Submission #1049622

#TimeUsernameProblemLanguageResultExecution timeMemory
10496228pete8Colors (BOI20_colors)C++17
0 / 100
1 ms428 KiB
#include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<cassert> #include<unordered_map> #include <queue> #include <cstdint> #include<cstring> #include<limits.h> #include<cmath> #include<set> #include<algorithm> #include <iomanip> #include<numeric> #include<bitset> using namespace std; #define ll long long #define f first #define s second #define pii pair<int,int> #define ppii pair<int,pii> #define vi vector<int> #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define ub upper_bound #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #pragma GCC optimize ("03,unroll-lopps") #define int long long using namespace std; const int mod=998244353,mxn=2e5+5,inf=1e18,minf=-1e18,lg=25; int n,m,k,x,q,t; map<int,int>here; int current=-1,C=0,cnt=0; int ans=inf,atleast=0; int test(int x){ if(current==-1)return 0; if(abs(current-x)>=C)return 1; return 0; } int ask(int x){ cout<<"? "<<x<<endl; cnt++; cout.flush(); here[x]=1; int a; cin>>a; //a=test(x); if(current!=-1){ if(a)ans=min(ans,abs(current-x)); else atleast=max(atleast,abs(current-x)); } current=x; return a; } int ask2(int x){ if(abs(x-current)<=atleast)return 0; if(abs(x-current)>=ans)return 1; cout<<"? "<<x<<endl; cnt++; cout.flush(); here[x]=1; int a; cin>>a; //a=test(x); if(current!=-1){ if(a)ans=min(ans,abs(current-x)); else atleast=max(atleast,abs(current-x)); } current=x; return a; } void answer(int x){ cout<<"= "<<x<<endl; cout.flush(); return; } int mid(int l,int r){return l+(r-l)/2;} int cur=0; void solve(){ //so scuff TT cin>>n; cnt=0; here.clear(); current=-1; ans=inf,atleast=0; srand(time(NULL)); int l1=1,r1=mid(1,n),l2=r1+1,r2=n; bool huh=1,side=1; while(r1-l1>1&&r2-l2>1){ if(abs((r1-l1)-(r2-l2))>1)assert(0); int mid1=mid(l1,r1),mid2=mid(l2,r2); int x,lc=0; if(r1-l1==r2-l2){ int lol=rand()%2;//i swear if this works TT if(lol)lc=1; } if(r1-l1>r2-l2||lc){ ask(mid1); x=ask2(mid2); side=1; } else{ ask(mid2); x=ask2(mid1); side=0; } if(x)l1=mid1+1,r2=mid2-1,huh=1; else r1=mid1-1,l2=mid2+1,huh=0; } vector<int>v; int left=r1-l1+1+(!side),right=r2-l2+1+side; if(abs(right-left)>=2){ //switch side if(right>left)ask(r2); else ask(l1); side^=1; huh=1; } for(int j=l1;j<=r1;j++)v.pb(j); for(int j=l2;j<=r2;j++)v.pb(j); for(int i=0;i<10;i++){ int furthest=-1; int closest=-1; if(huh){ for(auto j:v)if(!here[j]&&(furthest==-1||abs(current-j)>abs(current-furthest)))furthest=j; } if(!huh){ if(side){ for(int j=r1;j>=l1;j--)if(!here[j]){ closest=j; break; } } else{ for(int j=l2;j<=r2;j++)if(!here[j]){ closest=j; break; } } side^=1; } if(furthest==-1&&closest==-1)break; if(furthest!=-1)ask(furthest); else ask(closest); } int check=1; if(ans==inf)return void(answer(n)); //if(ans-atleast>2)assert(0); if(ans-atleast==1)return void(answer(ans)); for(int i=ans-1;i>atleast;i--){ if(current-i>=1&&!here[current-i])ask(current-i); else if(current+i<=n&&!here[current+i])ask(current+i); else{ while(check+i<=n){ if(here[check]==0&&here[check+i]==0){ ask(check); ask(check+i); break; } check++; } } if(ans==i)break; } answer(ans); } int32_t main(){ fastio //cin>>t; t=1; while(t--)solve(); } /* keep range l1,r1 and l2,r2 we can then qry mid=mid(l1,r1) to mid2=mid(l2,r2) then move to (mid+1,r1) and (l2,mid2-1) or (l1,mid-1) and (mid2+1,r2) until length if range1 or 2 ==1 abs(length1-length2) should always be <=1 problems->this will skip some range skip odd/even range ex. {a,b} , {c,d,e}+current 2 : 4 a,b : current,c,d,e C>=(current-(b+1)) */

Compilation message (stderr)

Colors.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
Colors.cpp:40:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   40 | int test(int x){
      |               ^
Colors.cpp:45:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   45 | int ask(int x){
      |              ^
Colors.cpp:60:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   60 | int ask2(int x){
      |               ^
Colors.cpp:77:18: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   77 | void answer(int x){
      |                  ^
Colors.cpp:82:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   82 | int mid(int l,int r){return l+(r-l)/2;}
      |                    ^
Colors.cpp:84:12: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   84 | void solve(){
      |            ^
Colors.cpp:172:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  172 | int32_t main(){
      |              ^
#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...