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

人生第一次交互题ac!

其实比较水

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

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

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

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

cntc亦然。

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

  • 所以对于cntr=cntc=2的,我们知道如下图这四个交点的位置上有两个头,再查询4次就行了。总次数为2*n+4<=2004<2019

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

  • 对于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;
}
}
上一篇:phpadmin增加使得项目能连接数据库


下一篇:CF1153E Serval and Snake(交互题)