제출 #262722

#제출 시각아이디문제언어결과실행 시간메모리
262722Coroian_David커다란 상품 (IOI17_prize)C++11
20 / 100
99 ms760 KiB
#include <bits/stdc++.h> //#include "prize.h" #define MAX_N 200000 using namespace std; typedef long long lint; vector<int> ask(int i); int N; int mx; int rez = -1; int spec[MAX_N + 1]; vector <int> doAsk(int poz) { if(rez != -1) return {0, 0}; vector <int> a = ask(poz - 1); if(a[0] + a[1] == 0) rez = poz; return a; } int px; int cst, cdr; bool verif(int poz) { if(rez != -1) return 0; vector <int> a = doAsk(poz); if(a[0] + a[1] == mx) { cst = a[0]; cdr = a[1]; px = poz; return 1; } spec[poz] = 1; return 0; } void intreaba(int poz) { int n = N; if(rez != -1) return; if(verif(poz)) return; int st = poz - 1; int dr = poz + 1; while(st >= 1 || dr <= n) { if(st >= 1) { if(verif(st)) return; st --; } if(dr <= n) { if(verif(dr)) return; dr ++; } } } void divide(int st, int dr, int pst, int pdr, int cate) { if(rez != -1) return; if(st > dr || cate == 0) return; if(st == dr && cate == 1) { spec[st] = 1; doAsk(st); return; } int mid = (st + dr) >> 1; intreaba(mid); divide(st, px - 1, pst, cdr, cst - pst); divide(px + 1, dr, cst, pdr, cdr - pdr); } int find_best(int n) { N = n; if(n <= 5000) { for(int i = 0; i < n; i ++) { vector<int> a = ask(i); if(a[0] + a[1] == 0) return i; } assert(1 == 0); //return; } srand(time(0)); for(int i = 1; i <= 10; i ++) { lint poz = 1LL * rand() * rand() % n; vector <int> a = ask(poz); if(a[0] + a[1] == 0) return poz; mx = max(mx, a[0] + a[1]); } divide(1, n, 0, 0, mx); return rez - 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...