Submission #951147

#TimeUsernameProblemLanguageResultExecution timeMemory
951147koukirocksColors (BOI20_colors)C++17
22 / 100
1 ms500 KiB
#include <bits/stdc++.h> #define speed ios_base::sync_with_stdio(0); cin.tie(0) #define all(x) (x).begin(),(x).end() #define F first #define S second using namespace std; typedef long long ll; typedef double db; typedef long double ldb; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const ll MAX=2e5+10,P=998244353; const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f; int n; int main() { speed; cin>>n; if (n<=64) { int now=1; int x; cout<<"? 1\n"<<flush; cin>>x; for (int i=1;i<n;i++) { now+=(i&1?1:-1)*(n-i); cout<<"? "<<now<<"\n"<<flush; cin>>x; if (x==0) { cout<<"= "<<(n-i+1)<<"\n"<<flush; return 0; } } cout<<"= 1\n"<<flush; } else if (n<=125) { int now=n+1>>1; int sml; cout<<"? "<<now<<"\n"<<flush; cin>>sml; cout<<"? 1\n"<<flush; cin>>sml; if (sml) { n=(n+1>>1)-1; now=1; for (int i=1;i<n;i++) { now+=(i&1?1:-1)*(n-i); int x; cout<<"? "<<now<<"\n"<<flush; cin>>x; if (x==0) { cout<<"= "<<(n-i+1)<<"\n"<<flush; return 0; } } cout<<"= 1\n"<<flush; } else { n=(n+1>>1)-1; now=1; for (int i=1;i<n;i++) { now+=(i&1?1:-1)*(2*n-i+1); int x; cout<<"? "<<now<<"\n"<<flush; cin>>x; if (x==0) { cout<<"= "<<(2*n-i+2)<<"\n"<<flush; return 0; } } cout<<"= "<<n+1<<"\n"<<flush; } } else if (n<=1000) { int k=sqrt(n); //1~k , k+1~2k , ... , k*k+1~n int cnt=k+(k*k!=n); int now=cnt>>1; int x; cout<<"? "<<now*k+1<<"\n"<<flush; cin>>x; int gp=k+1; for (int i=1;i<=k;i++) { now+=((i&1) xor (cnt%2==0)?1:-1)*i; cout<<"? "<<min(now*k+1,n)<<"\n"<<flush; cin>>x; if (x==1) { gp=i; break; } } // cout<<gp<<"\n"; // (gp-1)*k ~ gp*k-1 now=min(now*k+1,n); int dir=0; if (now>n/2) dir=1; if (gp==k+1) { for (int gap=min(gp*k,n)-1;gap>=(gp-1)*k+1;gap--) { if (dir) now-=gap; else now+=gap; dir^=1; cout<<"? "<<now<<"\n"<<flush; cin>>x; if (x==0) { cout<<"= "<<gap+1<<"\n"<<flush; return 0; } } cout<<"= "<<(gp-1)*k+1<<"\n"<<flush; } else { for (int gap=min(gp*k-1,n);gap>=(gp-1)*k+1;gap--) { if (dir) now-=gap; else now+=gap; dir^=1; cout<<"? "<<now<<"\n"<<flush; cin>>x; if (x==0) { cout<<"= "<<gap+1<<"\n"<<flush; return 0; } } cout<<"= "<<(gp-1)*k+1<<"\n"<<flush; } } return 0; }

Compilation message (stderr)

Colors.cpp: In function 'int main()':
Colors.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int now=n+1>>1;
      |           ~^~
Colors.cpp:45:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |    n=(n+1>>1)-1;
      |       ~^~
Colors.cpp:59:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |    n=(n+1>>1)-1;
      |       ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...