제출 #213045

#제출 시각아이디문제언어결과실행 시간메모리
213045Nucleist커다란 상품 (IOI17_prize)C++14
97.27 / 100
181 ms1656 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; } }; 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 find_best(int n) { int county=0; rod=0;belek=n-1; for (int i = 0; i < min(n,474); ++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=474; 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); if(k[0]+k[1]==0)return index; county++; //if(index==3273)debug(1) vis[index]=1; gg[index]=k; yo[k].insert(index); bool ka=true,ka1=true; bool na=false; if(k[0]+k[1]==kal)na=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!=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<indexa)ka=false; }*/ if(ka && !vis[(l+indexa)/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; } //koua

컴파일 시 표준 에러 (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:86:10: warning: variable 'na' set but not used [-Wunused-but-set-variable]
     bool na=false;
          ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...