Submission #761253

#TimeUsernameProblemLanguageResultExecution timeMemory
761253Dan4LifeLibrary (JOI18_library)C++17
100 / 100
250 ms592 KiB
#include <bits/stdc++.h> #include "library.h" using namespace std; #define pb push_back #define sz(a) (int)a.size() int n; vector<pair<int,int>> ed; vector<int> ans, adj[1500]; void dfs(int s, int p){ ans.pb(s); for(auto u : adj[s]) if(u!=p) dfs(u,s); } int chk(int l, int r, int q){ int ans = 0; for(auto [a,b] : ed) ans+=a>=l and b<=r; return r-l+1-q-ans>0; } void Solve(int N) { n = N; int tot = 0; vector<int> M(N,0); while(tot<n-1){ int l = 1, r = n; while(l<r){ int mid = (l+r)/2; fill(begin(M),begin(M)+mid,1); if(chk(1,mid,Query(M))) r=mid; else l=mid+1; fill(begin(M),begin(M)+mid,0); } int i = l; l = 1, r = i; while(l<r){ int mid = (l+r+1)/2; fill(begin(M)+mid-1,begin(M)+i,1); if(chk(mid,i,Query(M))) l=mid; else r=mid-1; fill(begin(M)+mid-1,begin(M)+i,0); } adj[i].pb(l), adj[l].pb(i), ed.pb({l,i}); tot++; } for(int i = 1; i <= N; i++){ if(sz(adj[i])<=1){ dfs(i,-1), Answer(ans); return; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...