Submission #347259

#TimeUsernameProblemLanguageResultExecution timeMemory
347259jamezzzLibrary (JOI18_library)C++14
100 / 100
342 ms620 KiB
#include <bits/stdc++.h> #include "library.h" using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> pbds; //less_equal for identical elements #define fi first #define se second #define pb emplace_back #define ll long long #define INF 1023456789 #define INFll 1023456789123456789 #define all(x) x.begin(), x.end() typedef pair<int, int> ii; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; int n; vector<int> m, ans; pbds s; int qry(int l, int r){ for (int i = l; i <= r; ++i){ m[*s.find_by_order(i)] = 1; } int res = Query(m); for (int i = 0; i < n; ++i) m[i] = 0; return res; } void Solve(int N){ if (N == 1){ vector<int> v; v.pb(1); Answer(v); return; } n = N; m.resize(n, 1); int ept; for (int i = 0; i < n; ++i){ m[i] = 0; if (Query(m) == 1){ ept = i; break; } m[i] = 1; } ans.pb(ept + 1); for (int i = 0; i < n; ++i){ m[i] = 0; if (ept != i) s.insert(i); } //printf("ept: %d\n", ept + 1); while (s.size()){ int lo = 0, hi = s.size() - 1, mid, res; while (lo <= hi){ mid = (lo + hi) / 2; m[ept] = 1; int t1 = qry(lo, mid); int t2 = qry(lo, mid); if (t1 == t2 + 1){ lo = mid + 1; } else{ hi = mid - 1; res = mid; } } ept = *s.find_by_order(res); s.erase(ept); ans.pb(ept + 1); //printf("ans: %d\n", ept + 1); } Answer(ans); }

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:43:25: warning: 'ept' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |     m.resize(n, 1); int ept;
      |                         ^~~
library.cpp:72:35: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |         ept = *s.find_by_order(res);
      |                                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...