제출 #62754

#제출 시각아이디문제언어결과실행 시간메모리
62754qkxwsm도서관 (JOI18_library)C++17
100 / 100
791 ms592 KiB
/* PROG: source LANG: C++11 _____ .' '. / 0 0 \ | ^ | | \ / | \ '---' / '._____.' */ #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> #include "library.h" using namespace std; using namespace __gnu_pbds; struct chash { int operator()(int x) const { x ^= (x >> 20) ^ (x >> 12); return x ^ (x >> 7) ^ (x >> 4); } int operator()(long long x) const { return x ^ (x >> 32); } }; template<typename T> using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T, typename U> using hashtable = gp_hash_table<T, U, chash>; template<class T> void readi(T &x) { T input = 0; bool negative = false; char c = ' '; while (c < '-') { c = getchar(); } if (c == '-') { negative = true; c = getchar(); } while (c >= '0') { input = input * 10 + (c - '0'); c = getchar(); } if (negative) { input = -input; } x = input; } template<class T> void printi(T output) { if (output == 0) { putchar('0'); return; } if (output < 0) { putchar('-'); output = -output; } int aout[20]; int ilen = 0; while(output) { aout[ilen] = ((output % 10)); output /= 10; ilen++; } for (int i = ilen - 1; i >= 0; i--) { putchar(aout[i] + '0'); } return; } template<class T> void ckmin(T &a, T b) { a = min(a, b); } template<class T> void ckmax(T &a, T b) { a = max(a, b); } template<class T> T normalize(T x, T mod = 1000000007) { return (((x % mod) + mod) % mod); } long long randomizell(long long mod) { return ((1ll << 45) * rand() + (1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod; } int randomize(int mod) { return ((1ll << 15) * rand() + rand()) % mod; } #define y0 ___y0 #define y1 ___y1 #define MP make_pair #define MT make_tuple #define PB push_back #define PF push_front #define LB lower_bound #define UB upper_bound #define fi first #define se second #define debug(x) cerr << #x << " = " << x << endl; const long double PI = 4.0 * atan(1.0); const long double EPS = 1e-10; #define MAGIC 347 #define SINF 10007 #define CO 1000007 #define INF 1000000007 #define BIG 1000000931 #define LARGE 1696969696967ll #define GIANT 2564008813937411ll #define LLINF 2696969696969696969ll #define MAXN 1013 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ld, ld> pdd; typedef vector<int> vi; int N; vi quer; vi cand; vi ans; int edges(int lt, int rt, int u) { for (int i = 0; i < N; i++) { quer[i] = 0; } for (int i = lt; i <= rt; i++) { quer[cand[i]] = 1; } if (u != -1) { quer[u] = 1; } return (rt - lt) + (bool) (u != -1) - Query(quer); } bool check_edge(int x) { for (int i = 0; i < N; i++) { quer[i] = 1; } quer[x] = 0; return (Query(quer) == 1); } int go(int u, int lt, int rt) { if (lt == rt) { return cand[lt]; } int mid = (lt + rt) / 2; int ledge = edges(lt, mid, u) - edges(lt, mid, -1); if (ledge) { rt = mid; } else { lt = mid + 1; } return go(u, lt, rt); } void Solve(int n) { N = n; quer.resize(N); cand.resize(N); ans.resize(N); if (N == 1) { Answer(vector<int>(1, 1)); return; } //find any guy on the edge: for (int i = 0; i < N; i++) { cand[i] = i; } for (int i = 0; i < N; i++) { if (check_edge(i)) { ans[0] = i; cand.erase(find(cand.begin(), cand.end(), i)); break; } } for (int i = 1; i < N; i++) { ans[i] = (go(ans[i - 1], 0, cand.size() - 1)); cand.erase(find(cand.begin(), cand.end(), ans[i])); } for (int i = 0; i < N; i++) { ans[i]++; } if (randomize(2)) { reverse(ans.begin(), ans.end()); } Answer(ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...