Submission #833908

#TimeUsernameProblemLanguageResultExecution timeMemory
833908maomao90Chameleon's Love (JOI20_chameleon)C++17
24 / 100
60 ms2440 KiB
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> #include "chameleon.h" using namespace std; #define REP(i, s, e) for (int i = (s); i < (e); i++) #define RREP(i, s, e) for (int i = (s); i >= (e); i--) template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} typedef unsigned long long ull; typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define SZ(_a) (int) _a.size() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005ll; const int MAXN = 1005; namespace { mt19937 rnd(8); int n; int occ[MAXN][MAXN]; } void Solve(int N) { n = N; //vi lid(n), rid(n); //iota(ALL(lid), 1); //iota(ALL(rid), n + 1); vi id(2 * n); iota(ALL(id), 1); vi lid, rid; for (int i : id) { lid.pb(i); if (Query(lid) != SZ(lid)) { lid.pop_back(); rid.pb(i); } } while (SZ(lid) != n) { lid.clear(); rid.clear(); shuffle(ALL(id), rnd); for (int i : id) { lid.pb(i); if (Query(lid) != SZ(lid)) { lid.pop_back(); rid.pb(i); } } } assert(SZ(lid) == n && SZ(rid) == n); REP (z, 0, 2) { for (int i : rid) { vi p(ALL(lid)); p.pb(i); int s = Query(p) - SZ(p); /* if (s == -1) { int lo = 0, hi = n - 1; while (lo < hi) { int mid = lo + hi >> 1; vi p(lid.begin(), lid.begin() + mid + 1); p.pb(i); int x = Query(p) - SZ(p); if (x <= s) { hi = mid; } else { lo = mid + 1; } } cerr << "ANSWER: " << i << ' ' << lid[hi] << '\n'; Answer(i, lid[hi]); continue; } */ int lo = 0, hi = n - 1; while (lo < hi) { int mid = lo + hi >> 1; vi p(lid.begin(), lid.begin() + mid + 1); p.pb(i); int x = Query(p) - SZ(p); if (x <= s) { hi = mid; } else { lo = mid + 1; } } cerr << i << ' ' << lid[hi] << '\n'; occ[min(i, lid[hi])][max(i, lid[hi])]++; lo = 0, hi = n - 1; while (lo < hi) { int mid = lo + hi + 1 >> 1; vi p(lid.begin() + mid, lid.end()); p.pb(i); int x = Query(p) - SZ(p); if (x <= s) { lo = mid; } else { hi = mid - 1; } } cerr << i << ' ' << lid[lo] << '\n'; occ[min(i, lid[lo])][max(i, lid[lo])]++; } swap(lid, rid); } REP (i, 1, 2 * n + 1) { REP (j, i + 1, 2 * n + 1) { if (occ[i][j] >= 2) { cerr << "ANSWER: " << i << ' ' << j << '\n'; Answer(i, j); } } } }

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:101:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |                 int mid = lo + hi >> 1;
      |                           ~~~^~~~
chameleon.cpp:115:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |                 int mid = lo + hi + 1 >> 1;
      |                           ~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...