Submission #765194

#TimeUsernameProblemLanguageResultExecution timeMemory
765194minhcoolLibrary (JOI18_library)C++17
100 / 100
269 ms18436 KiB
//#define local #ifndef local #include "library.h" #endif #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; //#define int long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 3e5 + 5; const int oo = 1e18 + 7, mod = 1e9 + 7; mt19937 rng(1); int rnd(int l, int r){ int temp = rng() % (r - l + 1); return abs(temp) + l; } set<int> Adj[N]; int ans[1005][1005]; int n; #ifdef local int Query(vector<int> v){ cout << "? "; for(auto it : v) cout << it << " "; cout << "\n"; int x; cin >> x; return x; } void Answer(vector<int> v){ cout << "! "; for(auto it : v) cout << it << " "; cout << "\n"; exit(0); } #endif int cal(int i2, int le, int ri){ // if(ans[le][ri]) return ans[le][ri]; //cout << i2 << " " << le << " " << ri << "\n"; if(le > ri) return 1; vector<int> v(n); for(int i = 0; i < n; i++) v[i] = 0; v[i2 - 1] = 1; for(int i = le - 1; i <= ri - 1; i++) v[i] = 1; return ans[le][ri] = Query(v); } bool vis[N]; vector<int> arr; void dfs(int u, int p){ arr.pb(u); for(auto v : Adj[u]) if(v != p) dfs(v, u); } void Solve(int N){ n = N; for(int i = 1; i < n; i++){ int lst = i; while(Adj[i].size() < 2){ int le = lst + 1, ri = n; if(le > ri) break; //if(cal(i, lst + 1, ri) > cal(lst + 1, lst + 1, ri)) break; while(le < ri){ int mid = (le + ri) >> 1; if(cal(i, lst + 1, mid) > cal(lst + 1, lst + 1, mid)) le = mid + 1; else ri = mid; } //cout << "OKAY " << i << " " << le << "\n"; Adj[i].insert(le); Adj[le].insert(i); lst = le; } } vector<int> er; for(auto it : Adj[n]){ if(cal(it, n, n) > 1) er.pb(it); } for(auto it : er){ Adj[it].erase(n); Adj[n].erase(it); } int st = -1; for(int i = 1; i <= n; i++) if(Adj[i].size() <= 1) st = i; dfs(st, st); Answer(arr); } #ifdef local void process(){ int n; cin >> n; int x; for(int i = 0; i < n; i++) cin >> x; Solve(n); } signed main(){ // ios_base::sync_with_stdio(0); // cin.tie(0); process(); } #endif

Compilation message (stderr)

library.cpp:22:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...