제출 #263373

#제출 시각아이디문제언어결과실행 시간메모리
263373Coroian_David커다란 상품 (IOI17_prize)C++11
0 / 100
1 ms504 KiB
#include <bits/stdc++.h> //#include "prize.h" #define MAX_N 200000 #define xx first #define yy second using namespace std; typedef long long lint; vector<int> ask(int i); int N; int mx; int rez = -1; int spec[MAX_N + 1]; int xd[MAX_N + 1]; pair <int, int> q[MAX_N + 1]; vector <int> tmp; int ST, DR; int aib[MAX_N + 1]; void baga(int poz, int nr) { while(poz <= N) { aib[poz] += nr; poz += poz & (-poz); } } int getSum(int poz) { int rez = 0; while(poz > 0) { rez += aib[poz]; poz -= poz & (-poz); } return rez; } int getS(int st, int dr) { int rez = getSum(dr); rez -= getSum(st - 1); return rez; } vector <int> doAsk(int poz) { if(rez != -1) return {0, 0}; if(xd[poz] == 1) { tmp[0] = q[poz].xx; tmp[1] = q[poz].yy; return tmp; } xd[poz] = 1; vector <int> a = ask(poz - 1); q[poz] = {a[0], a[1]}; if(a[0] + a[1] == 0) rez = poz; else if(a[0] + a[1] < mx) { spec[poz] = 1; baga(poz, 1); if(a[0] == 0) ST = max(ST, poz); if(a[1] == 0) DR = min(DR, poz); } return a; } bool verif(int poz, int &cst, int &cdr, int &px) { 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 &cst, int &cdr, int &px) { int n = N; if(rez != -1) return; if(verif(poz, cst, cdr, px)) return; int st = poz - 1; int dr = poz + 1; while(st >= 1 || dr <= n) { if(st >= 1) { if(verif(st, cst, cdr, px)) return; st --; } if(dr <= n) { if(verif(dr, cst, cdr, px)) return; dr ++; } } } void divide(int st, int dr, int pst, int pdr, int cate) { if(rez != -1) return; st = max(st, ST); dr = min(dr, DR); if(st > dr || cate == 0) return; int nou = cate - getS(st, dr); if(nou <= 0) return; cout << " SUNTEM " << st << " " << dr << " AVEM INSRE ST " << pst << " DR " << pdr << " " << cate << "\n"; if((dr - st + 1) - cate <= 1) { for(int i = st; i <= dr; i ++) doAsk(i); return; } int cst, cdr, px; int mid = (st + dr) >> 1; intreaba(mid, cst, cdr, px); divide(st, px - 1, pst, cdr, cst - pst); divide(px + 1, dr, cst, pdr, cdr - pdr); } int find_best(int n) { ST = 1; DR = n; N = n; tmp.resize(2); 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 <= 20; i ++) { lint poz = 1LL * rand() * rand() % n; vector <int> a = doAsk(poz + 1); 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...