Submission #1048577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048577		8pete8	Colors (BOI20_colors)	C++17	43 / 100	1 ms	600 KiB

Colors

#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){
    cnt++;
    cout<<"? "<<x<<endl;
    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;
    here.clear();
    current=-1;
    ans=inf,atleast=0;
    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);
        //edge case: r1-l1==r2-l2 where to go???? TT
        int x;
        if(r1-l1>r2-l2){
            ask(mid1);
            x=ask(mid2);
            side=1;
        }
        else{
            ask(mid2);
            x=ask(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;
    for(int j=l1;j<=r1;j++)v.pb(j);
    for(int j=l2;j<=r2;j++)v.pb(j);
    //cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<" "<<current<<" "<<huh<<' '<<side<<"LL\n";
    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));
    if(current-ans+1>=1&&!here[current-ans+1])ask(current-ans+1);
    else if(current+ans-1<=n&&!here[current+ans-1])ask(current+ans-1);
    else{
        while(check+ans-1<=n){
            if(here[check]==0&&here[check+ans-1]==0){
                ask(check);
                ask(check+ans-1);
                break;
            }
            check++;
        }
    }
    answer(ans);
}
int32_t main(){
    fastio
   // cin>>t;
  	t=1;
    while(t--)solve();
}
/*
n<=1000 can do sqrt decomp


2logn sol???
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

current problem-> unevenly splits between l1,r1,l2,r2 and current after the bsearch
how to fix? -> cant??
*/

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:18: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   60 | void answer(int x){
      |                  ^
Colors.cpp:65:20: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   65 | int mid(int l,int r){return l+(r-l)/2;}
      |                    ^
Colors.cpp:67:12: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   67 | void solve(){
      |            ^
Colors.cpp:140:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  140 | int32_t main(){
      |              ^

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 33