Submission #1049632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049632		8pete8	Colors (BOI20_colors)	C++17	43 / 100	1 ms	596 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){
    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(){
      |              ^

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