Submission #212935

#	Time	Username	Problem	Language	Result	Execution time	Memory
212935		Nucleist	The Big Prize (IOI17_prize)	C++14	20 / 100	315 ms	2936 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; }
};
int kal;
map<ve,set<int>>yo;
map<int,ve>gg;
int ans=0;
bool vis[200001];
set<int>curi;
int find_best(int n)
{ 
    for (int i = 0; i < min(n,470); ++i)
    {
        ve sal=ask(i);
        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);
    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;
    debug(index)
    int l=u.second.first;
    int r=u.second.second;
    vis[index]=1;

    ve k = ask(index);
    while(k[0]+k[1]!=kal && index<r)
    {
        if(k[0]==0 && k[1]==0){return index;}
        else
        {
            for(auto it:gg)
            {
                if(it.first<index)
                {
                    auto cur=it.second;
                    yo[it.second].erase(it.first);
                    it.second[1]--;
                    yo[it.second].insert(it.first);
                }
            }
            curi.insert(index);
        }
        index++;
        if(!vis[index]){k=ask(index);vis[index]=1;}
        else k=gg[index];
    }

    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;
        if(u<index)ka=false;
    }

    if(ka && !vis[(l+index)/2])q.push({(l+index)/2,{l,index}});
    if(ka1 && !vis[(index+r)/2])q.push({(index+r)/2,{index,r}});
    }
    return 0;
}
//code the AC sol !
// BS/queue/map

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