CF1153E Serval and Snake
2024-08-29 12:31:43
这是一道交互题
由于只需要确定起点和终点
你选择的矩形会将整个矩形分成的两个部分
如果起点和终点在同一个部分里,那么很显然回答应该是个偶数
反之则为奇数
因此我们可以先通过
int i;
for (i = 1; i < n; i++) {
printf("? 1 1 %d %d\n", n, i);
fflush(stdout);
scanf("%d", &x);
if (x & 1) break;
}
来确定起点和终点是否在同一列
如果不在同一列(即 \(i!=n\) ),那么 \(i\) 即为起点和终点这两个点中靠左的那个点所在的列
那么同理可以找到起点和终点这两个点中靠右的那个点所在的列
如果在同一列(即 \(i==n\) ) ,那么他们肯定不会在同一行(因为起点和终点是不同的点)
那么可以用同样的方法将两个点确定在两行内
现在已经能够锁定两个点在哪两条(行或列)了
在一条中确定一个点,二分再用奇偶判断即可
这样最坏的询问次数为 \(999+1000+10+10=2019\)
正好!
#include <bits/stdc++.h>
using namespace std;
int n, x, i, j;
int ax1, ay1, ax2, ay2;
int main() {
cin >> n;
for (i = 1; i < n; i++) {
printf("? 1 1 %d %d\n", n, i);
fflush(stdout);
scanf("%d", &x);
if (x & 1) break;
}
if (i != n) {
for (j = n; j > 1; j--) {
printf("? 1 %d %d %d\n", j, n, n);
fflush(stdout);
scanf("%d", &x);
if (x & 1) break;
}
int l = 1, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
printf("? %d %d %d %d\n", mid, i, n, i);
fflush(stdout);
scanf("%d", &x);
if (x & 1) l = mid;
else r = mid - 1;
}
ax1 = l, ay1 = i;
l = 1, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
printf("? %d %d %d %d\n", mid, j, n, j);
fflush(stdout);
scanf("%d", &x);
if (x & 1) l = mid;
else r = mid - 1;
}
ax2 = l, ay2 = j;
} else {
for (i = 1; i < n; i++) {
printf("? 1 1 %d %d\n", i, n);
fflush(stdout);
scanf("%d", &x);
if (x & 1) break;
}
for (j = n; j > 1; j--) {
printf("? %d 1 %d %d\n", j, n, n);
fflush(stdout);
scanf("%d", &x);
if (x & 1) break;
}
int l = 1, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
printf("? %d %d %d %d\n", i, mid, i, n);
fflush(stdout);
scanf("%d", &x);
if (x & 1) l = mid;
else r = mid - 1;
}
ax1 = i, ay1 = l;
l = 1, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
printf("? %d %d %d %d\n", j, mid, j, n);
fflush(stdout);
scanf("%d", &x);
if (x & 1) l = mid;
else r = mid - 1;
}
ax2 = j, ay2 = l;
}
printf("! %d %d %d %d\n", ax1, ay1, ax2, ay2);
return 0;
}
最新文章
- kafka - advertised.listeners and listeners
- Centos7下dnscrypt-proxy安装
- 【Remoting】.Net remoting方法实现简单的在线升级(上篇:更新文件)
- 夺命雷公狗---DEDECMS----18dedecms之无可奈何标签-sql标签取出今天更新
- [安卓]我的安卓开发FAQ
- setrendertraget 上下颠倒
- CALayer实现点击屏幕放大或者缩小的一个圆
- Windows Service 之 详解(一)
- C++ Code_combobox
- bzoj 2693: jzptab 线性筛积性函数
- Search a 2D Matrix【python】
- 6. Shell 流程控制
- 使用FlashWavRecorder实现浏览器录制wav音频和上传音频文件,兼容IE8以上浏览器
- 团队作业4——第一次项目冲刺(Alpha版本)11.16
- poj 2886 线段树+反素数
- BZOJ1482 : [Balkan2017]Cats
- Nginx 500错误总结
- Linux mount 命令进阶
- 《剑指offer》第五十九题(滑动窗口的最大值)
- /文件和目录权限chmod /更改所有者和所属组chown/umask/隐藏权限lsattr/chattr
热门文章
- linux性能监控命令(vmstat、sar、iostat、netstat)
- AI GMM
- 6-STM32物联网开发WIFI(ESP8266)+GPRS(Air202)系统方案升级篇-优化升级(安装Apache (Web服务器)软件,测试HTTP)
- C语言的3种参数传递方式
- enex 转 md 格式的几种方式(免费版/氪金版)
- c选择排序算法
- codeforces487A
- [模板] dfs序, 树链剖分, 换根
- SpringCloud笔记三:Eureka服务注册与发现
- C#获取根目录的方法总结