QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#383441#6394. Turn on the LightinnovationWA 1ms3608kbC++141.8kb2024-04-09 14:12:462024-04-09 14:12:47

Judging History

你现在查看的是最新测评结果

  • [2024-04-09 14:12:47]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3608kb
  • [2024-04-09 14:12:46]
  • 提交

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!