제출 #136124

#제출 시각아이디문제언어결과실행 시간메모리
136124JustasZ커다란 상품 (IOI17_prize)C++14
96.23 / 100
66 ms964 KiB
#include "prize.h" #include <bits/stdc++.h> #define pb push_back #define all(a) a.begin(), a.end() #define sz(a) (int)a.size() #define x first #define y second #define debug(...) cout << "[" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "]\n" #define rd() abs((int)rng()) using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int>pii; const int maxn = 2e5 + 100; const int mod = 1e9 + 7; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); /*vector<int> ask(int i) { cout << "? " << i << endl; vector<int>a(2); cin >> a[0] >> a[1]; return a; }*/ map<int, vector<int> >mp; vector<int> askk(int i) { if(!mp.count(i)) mp[i] = ask(i); return mp[i]; } int bl = 250; int find_best(int n) { vector<int>a, b; if(n <= 5000) { for(int i = 0; i < n; i++) { a = askk(i); if(a[0] + a[1] == 0) return i; } } int mx = 0, st = 500; for(int i = 0; i < min(n, 500); i++) { a = askk(i); if(a[0] + a[1] == 0) return i; if(a[0] + a[1] > 30) { mx = a[0] + a[1]; st = i + 1; break; } mx = max(mx, a[0] + a[1]); } for(int i = st; i < n; i += bl) { int j = min(i + bl - 1, n - 1); int p = i; a = askk(p); while(a[0] + a[1] != mx) { if(a[0] + a[1] == 0) return p; p++; if(p > j) break; a = askk(p); } b = askk(j); while(b[0] + b[1] != mx) { if(b[0] + b[1] == 0) return j; j--; if(j < p) break; b = askk(j); } if(p < j) { int between = b[0] - a[0]; if(between != 0) { int it = p; while(it < j && between > 0) { a = askk(it); if(a[0] + a[1] != mx) { between--; if(a[0] + a[1] == 0) return it; } else { int l = it + 1, r = j - 1; while(l < r) { int mid = (l + r) / 2; b = askk(mid); if(b[0] + b[1] != mx) r = mid; else { if(b[0] > a[0]) r = mid - 1; else l = mid + 1; } } it = l; a = askk(it); --between; if(a[0] + a[1] == 0) return it; } ++it; } } } } }

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

prize.cpp: In function 'int find_best(int)':
prize.cpp:125:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...