Submission #1198902

#TimeUsernameProblemLanguageResultExecution timeMemory
1198902santialt2Highway Tolls (IOI18_highway)C++20
0 / 100
53 ms2536 KiB
#include "highway.h" #include <bits/stdc++.h> using namespace std; #define ll int #define vl vector<ll> #define pb push_back #define pll pair<ll, ll> #define vs vector<string> #define vb vector<bool> #define all(aaa) aaa.begin(), aaa.end() #define rall(aaa) aaa.rbegin(), aaa.rend() #define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++) #define IO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define ed "\n" #define fi first #define se second ll MOD = 1e9+7; /* ll A, B, N, s_, t_; ll ask(vl p){ ll c = 0; ff(i, s_, t_){ if(p[i] == 0){ c += A; } else{ c += B; } } //cout << "ASK " << c << ed; for(ll q : p){ cout << q; } cout << ed; return c; } void answer(ll a, ll b){ cout << a << " " << b; } ll qq = 0, qqq = 0;*/ void find_pair(ll n, vl U, vl V, ll a, ll b){ ll m = n-1; vl empty(m, 0); ll dist = ask(empty); dist /= a; //cout << "DIST " << dist << ed; ll l = 0, r = m-dist; //cout << ed; if(dist == 1){ ll cc = 0; while(r-l > 0){ ll mid = (l+r)/2; //cout << "L " << l << " -- R " << r << " -- M " << mid << ed; vl ac = empty; fill(ac.begin()+l, ac.begin()+mid+1, 1); ll cur = ask(ac); if(cur == dist*a){ //cout << "C1" << ed; l = mid+1; } else{ //cout << "C2" << ed; r = mid; } //cc = l; } answer(cc, cc+1); //qq = cc; //qqq = cc+1; return; } while(l <= r){ ll mid = l+(r-l)/2; //cout << "L " << l << " -- R " << r << " -- M " << mid << ed; vl ac = empty; fill(ac.begin()+l, ac.begin()+mid+1, 1); ll cur = ask(ac); if(cur == dist*a){ //cout << "C1" << ed; l = mid+1; } else if(cur == dist*b){ //cout << "C2" << ed; r = mid-1; } else{ //cout << "GG" << ed; ll x = dist*a; //cout << x << " "; for(ll start = mid; start >= 0; start--){ x -= a; x += b; //cout << x << " "; if(x == cur){ //cout << "AAAAAAAAAAAA "; answer(start, start+dist); //qq = start; //qqq = start+dist; return; } } } } } /* int main(){ cin >> N >> A >> B >> s_ >> t_; vl coso(N-1, 0); /*ff(i, 0, N){ ff(j, i+1, N){ s_ = i; t_ = j; find_pair(N, coso, coso, A, B); //cout << "COSO " << qq << " " << qqq << ed << "PP " << i << " " << j << ed << ed << ed << ed; if(qq != i || qqq != j){ return 0; } } } find_pair(N, coso, coso, A, B); return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...