QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#192850 | #6394. Turn on the Light | Bai_xiaobo | WA | 1ms | 3548kb | C++14 | 3.0kb | 2023-09-30 15:40:22 | 2023-09-30 15:40:23 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define ldb long double
#define ll long long
#define ull unsigned long long
#define ill __int128
#define pb push_back
#define PII pair<ll,ll>
#define inf 0x3f3f3f3f
#define inff 0x3f3f3f3f3f3f3f3f
#define mem(a,b) memset(a,b,sizeof a)
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define sc(a) scanf("%lf",&a);
const ll N = 1e6+10 ;
const ll mod = 1e9+7;
const ll esp=1e-6;
bool cmp(ll a,ll b){return a>b;}
ll lowbit(ll x){return x&-x;}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1,y=0;return a;}ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d;}
ll ksm(ll a,ll b,ll c){ll sum=1;while(b){if(b&1)sum=sum*a%c;a=a*a%c;b>>=1;}return sum;}
ll addm(ll a,ll b,ll c){return (a%c+b%c)%c;}
ll faddm(ll a,ll b){return (((a%b)+b)%b);}
//inline void print(__int128 x){if(x<0){putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');}
//void read(__int128 &x){x=0;int f=1;char ch=getchar();while (!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}x*=f;}
//ll fact[N],infact[N];void init(ll n){fact[0]=1;for(int i=1;i<=n;i++) fact[i]=(fact[i-1]*i)%mod;infact[n]=ksm(fact[n],mod-2,mod);for(int i=n-1;i>=0;i--) infact[i]=infact[i+1]*(i+1)%mod;}ll cmb( ll a , ll b ){if(b>a) return 0 ;return (((fact[a]*infact[a-b])%mod)*infact[b])%mod ;}
//ll h[N],e[N*2],ne[N*2],w[N*2],idx;void add(ll a,ll b,ll c){e[idx]=b,ne[idx]=h[a],h[a]=idx,w[idx++]=c;}
//ll fa[N],siz[N];ll ifind(ll x){return x==fa[x]?x:fa[x]=ifind(fa[x]);}
ll ask(ll x)
{
cout<<"? "<<x<<"\n";
cout.flush() ;
ll z;
cin>>z;
return z;
}
void solve()
{
ll n;
cin>>n;
ll start=1;
ll last=1;
ll cnt=0;
ll l=0,r=0;
while(start<n)
{
ll u=ask(start);
if(u>cnt)//如果我当前的值大于上一个就继续找
{
cnt=u;
}
else if(u==cnt)//如果等于那一定就这一个
{
cout<<"! "<<start<<"\n";
cout.flush() ;
return;
}
else//如果小于上一个的话就已经确定了
{
l=last+1;//上一个
r=start-1;//这个
cnt=u;
break;
}
last=start;
start*=2ll;
}
if(l==0)
{
l=last+1;
r=n;
}
while(l<=r)
{
ll mid=l+r>>1;
ll z=ask(mid);
if(z==cnt)
{
cout<<"! "<<mid<<"\n";
cout.flush() ;
return;
}
else if(z<cnt)
{
r=mid-1;
cnt=z;
}
else
{
l=mid+1;
cnt=z;
}
}
}
int main(){
// ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
ll tt = 1;
// freopen("input.txt", "r", stdin);
// cin >> tt ;
while( tt-- ) solve() ;
return 0 ;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3340kb
input:
3 1 2 2
output:
? 1 ? 2 ? 3 ! 3
result:
ok Correct position at 3
Test #2:
score: 0
Accepted
time: 1ms
memory: 3400kb
input:
10 1 2 3 2 1 1
output:
? 1 ? 2 ? 4 ? 8 ? 6 ? 5 ! 5
result:
ok Correct position at 5
Test #3:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
9 1 2 3 2 1 1
output:
? 1 ? 2 ? 4 ? 8 ? 6 ? 5 ! 5
result:
ok Correct position at 5
Test #4:
score: 0
Accepted
time: 1ms
memory: 3360kb
input:
8 1 2 3 4 5 5
output:
? 1 ? 2 ? 4 ? 6 ? 7 ? 8 ! 8
result:
ok Correct position at 8
Test #5:
score: 0
Accepted
time: 0ms
memory: 3416kb
input:
7 1 2 3 2 2
output:
? 1 ? 2 ? 4 ? 6 ? 5 ! 5
result:
ok Correct position at 5
Test #6:
score: 0
Accepted
time: 0ms
memory: 3404kb
input:
6 1 2 3 3
output:
? 1 ? 2 ? 4 ? 5 ! 5
result:
ok Correct position at 5
Test #7:
score: 0
Accepted
time: 0ms
memory: 3412kb
input:
5 1 2 3 3
output:
? 1 ? 2 ? 4 ? 5 ! 5
result:
ok Correct position at 5
Test #8:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
4 1 2 3 3
output:
? 1 ? 2 ? 3 ? 4 ! 4
result:
ok Correct position at 4
Test #9:
score: 0
Accepted
time: 0ms
memory: 3280kb
input:
3 1 1
output:
? 1 ? 2 ! 2
result:
ok Correct position at 2
Test #10:
score: 0
Accepted
time: 1ms
memory: 3408kb
input:
2 1 1
output:
? 1 ? 2 ! 2
result:
ok Correct position at 2
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3328kb
input:
1
output:
result:
wrong answer format Unexpected end of file - token expected