제출 #302373

#제출 시각아이디문제언어결과실행 시간메모리
302373dantoh000커다란 상품 (IOI17_prize)C++14
20 / 100
57 ms512 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; int mx = 0; int ans = -1; vector<int> pos; void search(int ll, int lr, int rl, int rr, int cl, int cr, int c); void search(int L, int R, int cl, int cr, int c){ if (c == 0) return; //printf("searching %d %d %d %d %d\n",L,R,cl,cr,c); if (L == R){ //printf("add pos %d\n",L); //printf("check: %d\n",g[L]); pos.push_back(L); return; } if (L > R) return; int mid = (L+R)/2; //printf("mid %d\n",mid); search(L, mid, mid+1, R, cl, cr, c); return; } void search(int ll, int lr, int rl, int rr, int cl, int cr, int c){ if (c == 0) return; //printf("search <%d,%d><%d,%d>, <%d,%d>, %d\n",ll,lr,rl,rr,cl,cr,c); if (ll == rr){ search(ll, rr, cl, cr, c); return; } int CL, CR; int q = (rr-rl)>(lr-ll)?rl:lr; assert(q >= 0); vector<int> p = ask(q); CL = p[0], CR = p[1]; //printf("queried %d, got (%d,%d)\n",q,CL,CR); if (CL + CR != mx){ /// is special //printf("add pos %d\n",q); // printf("check: %d\n",g[q]); pos.push_back(q); if (q == lr){ if (ll <= lr-1) search(ll, lr-1, rl, rr, cl, cr, c-1); else search(rl, rr, cl+1, cr, c-1); } else if (q == rl){ if (rl+1 <= rr) search(ll, lr, rl+1, rr, cl, cr, c-1); else search(ll, lr, cl, cr+1, c-1); } return; } CR -= cr; CL -= cl; if (q == lr){ if (ll <= lr-1) search(ll, lr-1,cl,CR+cr,CL); search(rl, rr,CL+cl,cr,CR); } else{ search(ll, lr,cl,CR+cr,CL); if (rl+1 <= rr) search(rl+1, rr,CL+cl,cr,CR); } } int find_best(int n) { for (int i = 0; i < min(n,447); i++){ vector<int> p = ask(i); //if (p[0] == 0 && p[1] == 0) return i; mx = max(mx,p[0]+p[1]); } int L, R; L = 0, R = n-1; int mid = (L+R)/2; search(L, mid, mid+1, R, 0, 0, mx); // printf("%d , %d\n",pos.size(),nonmax); for (auto x : pos){ vector<int> p = ask(x); if (p[0] + p[1] == 0) return x; } assert(false); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...