Submission #1200149

#TimeUsernameProblemLanguageResultExecution timeMemory
1200149hengliaoFinding Routers (IOI20_routers)C++20
97 / 100
1 ms584 KiB
#include "routers.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); namespace{ vector<int> ans; const int mxl=1e5+5; vector<int> rec(mxl,-1); int query(int x){ if(rec[x]!=-1) return rec[x]; return rec[x]=use_detector(x); } } void go(int l,int r,int tl,int tr){ if(l==r){ return; } int mid=(l+r)/2; int L=tl,R=tr; while(L<R){ int M=(L+R+1)/2; if(query(M)<=mid){ L=M; } else{ R=M-1; } } ans[mid]=L; go(l,mid,tl,L-2); go(mid+1,r,L+2,tr); } std::vector<int> find_routers(int l, int n, int q) { ans=vector<int>(n); go(0,n-1,0,l); vector<int> val(n); for(int i=1;i<n;i++){ val[i]=ans[i-1]+(ans[i-1]-val[i-1]); } return val; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...