QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#383441 | #6394. Turn on the Light | innovation | WA | 1ms | 3608kb | C++14 | 1.8kb | 2024-04-09 14:12:46 | 2024-04-09 14:12:47 |
Judging History
answer
/*
有n盏灯. 一开始都是灭的. 我每次可以选一盏, 使得他亮
然后会被告知目标灯左边灯的数量-右边灯的数量的绝对值
那么 对于当前的灯
如果我添加一盏灯, 但灯绝对值没变, 那么一定是当前位置
那我二分找, 添一盏灯, 然后为了判断位置.
我右边最边界放一盏. 则右边会多一个. 如果当前左边更多, 会减少
如果当前右边更多, 会增加
那我先在中间放一个
如果目标在左边, 我右边放一个 他会增加
如果目标在右边, 我右边放一个 他会减少
往左走. 我中间放一个 //当前有值的情况下.
如果目标在左边, 增加
往左走, 如果我中间放一个.
则重复方法二
如果目标在右边, 减少
往右走, 如果我中间放一个
则也重复方法二.
往右走, 我中间放一个
如果目标在左边, 增加
如果目标在右边, 增加.
(这里再添一个最右边位置)
则重复方法一.
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll query(ll x)
{
cout<<"? "<<x<<endl;
cin>>x;
return x;
}
int main()
{
//ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n, ans, L, R, mid;
cin>>n;
ans = 0;
L = 1;
R = n;
while(L<=R)
{
mid = L+R>>1;
auto now = query(mid);
if(now==ans)
{
cout<<"! "<<mid<<endl;
return 0;
}
else if(ans>0)
{
if(now>ans)
{//如果中间位置放了后, 增加了, 在左侧
R = mid-1;
}
else if(now<ans)
{//如果减少了, 在右边
L = mid+1;
}
ans = now;
}
else if(ans==0)
{
ans = now;
auto nex = query(R);
if(nex==ans)
{
cout<<"! "<<R<<endl;
return 0;
}
else if(nex>ans)
{
R = mid-1;
}
else
{
L = mid+1;
}
ans = nex;
}
}
return 0;
}
//1 2 3
//
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
3 1 1
output:
? 2 ? 3 ! 3
result:
ok Correct position at 3
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3564kb
input:
10 1 0 1 1
output:
? 5 ? 10 ? 8 ? 10 ! 10
result:
wrong answer Wrong answer, more than 1 possible light!