Submission #503570

#TimeUsernameProblemLanguageResultExecution timeMemory
503570Koosha_mvLibrary (JOI18_library)C++14
100 / 100
282 ms496 KiB
#include <bits/stdc++.h> using namespace std; #define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl #define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl #define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl #define eror(x) cout<<#x<<'='<<(x)<<endl #define f_(i,a,b) for(int i=a;i>=b;i--) #define f(i,a,b) for(int i=a;i<b;i++) #define nb(x) __builtin_popcount(x) #define all(v) v.begin(),v.end() #define bit(n,k) (((n)>>(k))&1) #define Add(x,y) x=(x+y)%mod #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define lst(x) x[x.size()-1] #define sz(x) int(x.size()) #define mp make_pair #define ll long long #define pb push_back #define S second #define F first #include "library.h" const int N=2222; int n,a[N]; vector<int> res,g[N]; vector<pair<int,int> > ans; void dfs(int u,int p){ res.pb(u+1); for(auto v : g[u]){ if(v==p) continue ; dfs(v,u); } } int ask(int l,int r){ vector<int> M(n); f(i,l,r+1) M[i]=1; int res=r-l+1-Query(M); for(auto p : ans){ if(l<=p.F && p.F<=r && l<=p.S && p.S<=r){ res--; } } return res; } void Solve(int _n){ n=_n; f_(i,n-1,0){ int t=ask(i,n-1); while(t--){ int l=i,r=n-1; while(l+1<r){ int mid=(l+r)/2; if(ask(i,mid)){ r=mid; } else{ l=mid; } } int u=i,v=r; g[u].pb(v); g[v].pb(u); ans.pb({u,v}); } } f(i,0,n){ if(g[i].size()==1 || i==n-1){ dfs(i,i); Answer(res); return ; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...