제출 #212989

#제출 시각아이디문제언어결과실행 시간메모리
212989Nucleist커다란 상품 (IOI17_prize)C++14
0 / 100
118 ms860 KiB
#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=2000; int fat=0; int rod=0,belek=-1; int find_best(int n) { srand(time(NULL)); int county=0; rod=0;belek=n-1; if(county>=5000) 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++; if(county>=7000)a=0; 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; }

컴파일 시 표준 에러 (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")
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...