제출 #213014

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
213014		Nucleist	커다란 상품 (IOI17_prize)	C++14	20 / 100	671 ms	2680 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;
dos aski[200001];
map<ve,set<int>>yo;
map<int,ve>gg;
int ans=0;
bool vis[200001];
set<int>curi;
set<dos>koli;
int rod=0,belek=-1;

int findCeil(int arr[], int r, int l, int h)  
{  
    int mid;  
    while (l < h)  
    {  
        mid = l + ((h - l) >> 1); // Same as mid = (l+h)/2  
        (r > arr[mid]) ? (l = mid + 1) : (h = mid);  
    }  
    return (arr[l] >= r) ? l : -1;  
}  
  
// The main function that returns a random number 
// from arr[] according to distribution array  
// defined by freq[]. n is size of arrays.  
int myRand(int arr[], int freq[], int n)  
{  
    // Create and fill prefix array  
    int prefix[n], i;  
    prefix[0] = freq[0];  
    for (i = 1; i < n; ++i)  
        prefix[i] = prefix[i - 1] + freq[i];  
  
    // prefix[n-1] is sum of all frequencies. 
    // Generate a random number with  
    // value from 1 to this sum  
    int r = (rand() % prefix[n - 1]) + 1;  
  
    // Find index of ceiling of r in prefix arrat  
    int indexc = findCeil(prefix, r, 0, n - 1);  
    return arr[indexc];  
}  
  

int find_best(int n)
{ 
    int county=0;
    rod=0;belek=n-1;
    int sol[]={0,1};
    int freq[]={90,10};
    srand(time(NULL));
    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())
    {
    //debug(county)
    auto u=q.front();
    q.pop();
    
    int index=u.first;
    int indexa=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);
            }
            //if(index==3273)debug(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);
                }
            }
            //if(index==3273)debug(1)
            curi.insert(index);
        }
        index++;
        if(!vis[index]){k=ask(index);vis[index]=1;county++;}
        else k=gg[index];
    }
    //if(index==3273)debug(1)
    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(u<index)
        {
            ka=false;
            koli.insert({u,index});
        }
    }
    if(index==3273)debug(1)
    //if(index!=indexa)ka=true;
    /*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)
                {
                    auto cur=it.second;
                    yo[it.second].erase(it.first);
                    it.second[1]--;
                    yo[it.second].insert(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<iandexa)ka=false;
    }*/
    int a=myRand(sol,freq,2);
    if(index>=190200 && index<=199800)a=1;
    if(a){if(!vis[(l+indexa)/2])q.push({(l+indexa)/2,{l,indexa}});}
    else if(!vis[(l+index)/2])q.push({(l+index)/2,{l,index}});
    if(ka1 && !vis[(index+r)/2])q.push({(index+r)/2,{index,r}});
    
    }}
    //debug(county)
    return 0;
}

컴파일 시 표준 에러 (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")
 
prize.cpp: In function 'int find_best(int)':
prize.cpp:167:10: warning: variable 'ka' set but not used [-Wunused-but-set-variable]
     bool ka=true,ka1=true;
          ^~

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