제출 #390522

#제출 시각아이디문제언어결과실행 시간메모리
390522mehrdad_sohrabi커다란 상품 (IOI17_prize)C++14
20 / 100
87 ms11416 KiB
#include <bits/stdc++.h> #include "prize.h" using namespace std; typedef long long int ll; typedef complex<double> point; typedef long double ld; #define pb push_back #define pii pair < ll , ll > #define F first #define S second //#define endl '\n' #define int long long #define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #define kill(x) return cout<<x<<'\n', 0; const int N=2e5+100; /* static const int max_q = 10000; static int n; static int query_count = 0; static vector<int> g; static vector<vector<int> > rank_count; vector<int32_t> ask(int i) { query_count++; if(query_count > max_q) { cerr << "Query limit exceeded" << endl; exit(0); } if(i < 0 || i >= n) { cerr << "Bad index: " << i << endl; exit(0); } vector<int32_t> res(2); res[0] = rank_count[g[i] - 1][i + 1]; res[1] = rank_count[g[i] - 1][n] - res[0]; return res; } */ ll val[N]; pii a[N]; ll mx=0; pii ASK(int i){ if (val[i]==-1){ vector <int32_t> ans=ask(i); a[i]={ans[0],ans[1]}; val[i]=a[i].F+a[i].S; } return a[i]; } ll vis[N]; void solve(ll l,ll r,ll kl,ll kr){ if (kl+kr>=mx) return ; vector <int> cand; for (int i=l;i<r;i++){ if (!vis[i]){ cand.pb(i); } } ll s=cand.size(); s/=2; if (cand.size()==0) return ; if (cand.size()==1){ ASK(cand[0]); if (val[cand[0]]<mx){ vis[cand[0]]=1; } if (val[cand[0]]>mx) cout << 1/0; return ; } ll mid=cand[s-1]+1; for (int i=s;i<cand.size();i++){ ASK(cand[i]); if (val[cand[i]]<mx){ vis[cand[i]]=1; continue; } if (i!=cand.size()-1){ solve(cand[i+1],r,a[cand[i]].F,kr); } solve(l,mid,kl,a[cand[i]].S+i-s); return ; } solve(l,mid,kl,kr+cand.size()-s); } int32_t find_best(int32_t n) { memset(val,-1,sizeof val); vector <int> rnd; for (int i=0;i<n;i++){ rnd.pb(i); } random_shuffle(rnd.begin(),rnd.end()); for (int i=0;i<min(n,50);i++){ ASK(rnd[i]); mx=max(mx,val[rnd[i]]); } solve(0,n,0,0); for (int i=0;i<n;i++){ if (vis[i]==1 && val[i]==0) return i; } return 0; } /* int32_t main() { cin >> n; g.resize(n); for(int i = 0; i < n; i++) { //cin >> g[i]; g[i]=2; if(g[i] < 1) { cerr << "Invalid rank " << g[i] << " at index " << i << endl; exit(0); } } ll z=rand()%n; g[z]=1; cout << z << endl; int max_rank = *max_element(g.begin(), g.end()); rank_count.resize(max_rank + 1, vector<int>(n + 1, 0)); for(int r = 0; r <= max_rank; r++) { for(int i = 1; i <= n; i++) { rank_count[r][i] = rank_count[r][i - 1]; if(g[i - 1] == r) rank_count[r][i]++; } } for(int i = 0; i <= n; i++) for(int r = 1; r <= max_rank; r++) rank_count[r][i] += rank_count[r - 1][i]; int res = find_best(n); cout << res << endl << "Query count: " << query_count << endl; return 0; } */ /* 8 3 2 3 1 3 3 2 3 */

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'void solve(ll, ll, ll, ll)':
prize.cpp:69:39: warning: division by zero [-Wdiv-by-zero]
   69 |         if (val[cand[0]]>mx) cout << 1/0;
      |                                      ~^~
prize.cpp:73:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i=s;i<cand.size();i++){
      |                  ~^~~~~~~~~~~~
prize.cpp:79:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         if (i!=cand.size()-1){
      |             ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...