Submission #212984

#	Time	Username	Problem	Language	Result	Execution time	Memory
212984		Nucleist	The Big Prize (IOI17_prize)	C++14	20 / 100	1042 ms	2364 KiB

prize

#include "prize.h"
#include <bits/stdc++.h> 
using namespace std; 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<int>
#define dos pair<ll,ll>
#define vedos vector<dos>
//#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
dos aski[200001];
int kal;

map<ve,set<int>>yo;
map<int,ve>gg;
int ans=0;
bool vis[200001];
set<int>curi;
set<dos>koli;
int sam=3000;
int fat=0;
int rod=0,belek=-1;
int find_best(int n)
{ 
    srand (time(NULL));
    int county=0;
    rod=0;belek=n-1;
    for (int i = 0; i < min(n,470); ++i)
    {
        ve sal=ask(i);
        county++;
        int yol=sal[0]+sal[1];
        if(yol==0)return i;
        kal=max(kal,yol);
    }
    queue<pair<int,dos>>q;
    int low=470;
    int high=n-1;
    ve last=ask(n-1);
    county++;
    if(last[0]+last[1]==0)return n-1;
    int med=(low+high)/2;
    q.push({med,{low,high}});
    while(!q.empty())
    {
    auto u=q.front();
    q.pop();
    
    int index=u.first;
    int indexa=index;
   // debug(index)
    int l=u.second.first;
    int r=u.second.second;

    bool ki=true;
    for(auto it:koli)
    {
        if(l>=it.first && r<=it.second)
        {
            ki=false;break;
        }
    }
    if(ki)
    {
        if(vis[index] || (l>belek || r<rod))continue;
    vis[index]=1;

    ve k = ask(index);
    ve kaka=k;
    county++;
    while(k[0]+k[1]!=kal && index<r)
    {
        if(k[0]==0 && k[1]==0){
            debug(county);return index;
        }
        else
        {
            if(k[0]+k[1]==1)
            {
                if(k[0]==1){belek=min(belek,index-1);}
                else rod=max(rod,index+1);
            }
            for(auto it:gg)
            {
                if(it.first<index)
                {
                    ve cur;
                    cur.resize(2);
                    cur=it.second;
                    //if(index==3273)debugs(2,it.first);
                    if(yo.find(it.second)!=yo.end())yo[it.second].erase(it.first);
                    //if(index==3273)debugs(2,it.first);
                    ///if(index==3273)debug(cur[1])
                    cur[1]--;
                    //if(index==3273)debugs(2,it.first);
                    yo[cur].insert(it.first);
                    //if(index==3273)debugs(2,it.first);
                }
            }
            curi.insert(index);
        }
        index++;
        if(!vis[index]){k=ask(index);vis[index]=1;county++;}
        else k=gg[index];
    }
    int a=rand()%2;
    if(fat==sam)a=0;
    if(a==1)fat++;
    vis[index]=1;
    int indexi=0,indexi1=0;
    for(auto it:curi)
    {
        if(it<index)indexi++;
        else indexi1++;
    }
    k[0]-=indexi;
    k[1]-=indexi1;
    gg[index]=k;
    yo[k].insert(index);

    bool ka=true,ka1=true;
    if(yo.find(k)!=yo.end())
    {
        auto u=(*(yo[k].begin()));
        if(u>index){ka1=false;koli.insert({index,u});}
    }
    if(!a)
    {
      if(indexa!=index)
    {
    while(kaka[0]+kaka[1]!=kal && indexa>l)
    {
        if(kaka[0]==0 && kaka[1]==0){
            debug(county);
            return indexa;
        }
        else
        {
            if(kaka[0]+kaka[1]==1)
            {
                if(kaka[0]==1){belek=min(belek,indexa-1);}
                else rod=max(rod,indexa+1);
            }
            for(auto it:gg)
            {
                if(it.first<indexa)
                {
                    ve cur;
                    cur.resize(2);
                    cur=it.second;
                    //if(index==3273)debugs(2,it.first);
                    if(yo.find(it.second)!=yo.end())yo[it.second].erase(it.first);
                    //if(index==3273)debugs(2,it.first);
                    ///if(index==3273)debug(cur[1])
                    cur[1]--;
                    //if(index==3273)debugs(2,it.first);
                    yo[cur].insert(it.first);
                    //if(index==3273)debugs(2,it.first);
                }
            }
            curi.insert(indexa);
        }
        indexa--;
        if(!vis[indexa]){kaka=ask(indexa);vis[indexa]=1;county++;}
        else kaka=gg[indexa];
    }

    vis[indexa]=1;
    indexi=0,indexi1=0;
    for(auto it:curi)
    {
        if(it<indexa)indexi++;
        else indexi1++;
    }
    kaka[0]-=indexi;
    kaka[1]-=indexi1;
    gg[indexa]=kaka;
    yo[kaka].insert(indexa);
    if(yo.find(kaka)!=yo.end())
    {
        auto u=(*(yo[kaka].begin()));
        if(u<indexa){ka=false;koli.insert({u,indexa});}
    }
    }
    else
    {
        if(yo.find(k)!=yo.end())
    {
        auto u=(*(yo[k].begin()));
        if(u>index){
        ka1=false;
        koli.insert({index,u});}
        if(u<index)
        {
            ka=false;
            koli.insert({u,index});
        }
    }
    }
    if(ka && !vis[(l+indexa)/2])q.push({(l+indexa)/2,{l,indexa}});
    if(ka1 && !vis[(index+r)/2])q.push({(index+r)/2,{index,r}});
    
    } 
    else
    {
        if(yo.find(k)!=yo.end())
    {
        auto u=(*(yo[k].begin()));
        if(u>index){
        ka1=false;
        koli.insert({index,u});}
        if(u<index)
        {
            ka=false;
            koli.insert({u,index});
        }
    
    }
    if(ka && !vis[(l+indexa)/2])q.push({(l+indexa)/2,{l,indexa}});
    if(ka1 && !vis[(index+r)/2])q.push({(index+r)/2,{index,r}});
    } 
    }
    //if(index!=indexa)ka=true;
    
    
    
    }
    
    //debug(county)
    return 0;
}

Compilation message (stderr)

prize.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
prize.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80