人生第一次交互题ac！

其实比较水

容易发现如果查询的矩阵里面包含一个端点，得到的值是奇数；否则是偶数。

所以只要花2*n次查询每一行和每一列，找出其中查询答案为奇数的行和列，就表示这一行有一个端点。

令cntr表示答案为奇数的行数，cntc表示答案为奇数的列数。

那么cntr只能为0或者2，0就表示两个头在同一行，2就表示两个头在不同的行（我们已经找出这两行了）

cntc亦然。

然后cntr与cntc不可能同时为0，因为两个端点不可能既在同一行又在同一列。

所以对于cntr=cntc=2的，我们知道如下图这四个交点的位置上有两个头，再查询4次就行了。总次数为2*n+4<=2004<2019
对于cntr与cntc某一个为0的，即两个端点在同一行（列）的情况，已经确定了某两列（行），就随便选一列（行）二分答案就行了(集体看代码)。总次数为2*n+ ⌈log n⌉<=2010<2019

CODE

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 100005;

int n, r[2], cntr, c[2], cntc;

inline bool query(int A, int B, int C, int D) {

	printf("? %d %d %d %d\n", A, B, C, D);

	fflush(stdout); int x; scanf("%d", &x); return x&1;

}

bool flg[2][2];

int main () {

	scanf("%d", &n);

	for(int i = 1; i <= n; ++i) {

		if(query(i, 1, i, n)) r[cntr++] = i;

		if(query(1, i, n, i)) c[cntc++] = i;

	}

	if(cntr == cntc) {

		for(int i = 0; i < 2; ++i)

			for(int j = 0; j < 2; ++j)

				if(query(r[i], c[j], r[i], c[j]))

					flg[i][j] = 1;

		putchar('!');

		for(int i = 0; i < 2; ++i)

			for(int j = 0; j < 2; ++j)

				if(flg[i][j] == 1)

					printf(" %d %d", r[i], c[j]);

		putchar('\n');

		fflush(stdout);

		return 0;

	}

	else {

		if(!cntr) {

			int L = 1, R = n, mid;

			while(L < R) {

				mid = (L + R) >> 1;

				if(query(1, c[0], mid, c[0])) R = mid;

				else L = mid + 1;

			}

			printf("! %d %d %d %d\n", L, c[0], L, c[1]);

			fflush(stdout);

		}

		else {

			int L = 1, R = n, mid;

			while(L < R) {

				mid = (L + R) >> 1;

				if(query(r[0], 1, r[0], mid)) R = mid;

				else L = mid + 1;

			}

			printf("! %d %d %d %d\n", r[0], L, r[1], L);

			fflush(stdout);

		}

		return 0;

	}

}

cntc

Codeforces Round #551 (Div. 2) E. Serval and Snake (交互题)

CODE