Submission #833929

#TimeUsernameProblemLanguageResultExecution timeMemory
833929maomao90Chameleon's Love (JOI20_chameleon)C++17
64 / 100
52 ms2256 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 { int n; int occ[MAXN][MAXN]; vi adj[MAXN]; int label[MAXN]; void dfs(int u) { for (int v : adj[u]) { if (label[v]) { continue; } label[v] = 3 - label[u]; dfs(v); } } } void Solve(int N) { n = N; //vi lid(n), rid(n); //iota(ALL(lid), 1); //iota(ALL(rid), n + 1); vi lid, rid; if (n <= 50) { REP (i, 1, 2 * n + 1) { REP (j, i + 1, 2 * n + 1) { if (Query({i, j}) == 1) { adj[i].pb(j); adj[j].pb(i); } } } REP (i, 1, 2 * n + 1) { if (label[i]) { continue; } label[i] = 1; dfs(i); } REP (i, 1, 2 * n + 1) { if (label[i] == 1) { lid.pb(i); } else { rid.pb(i); } } } else { REP (i, 1, 2 * n + 1) { lid.pb(i); if (Query(lid) != SZ(lid)) { lid.pop_back(); rid.pb(i); } } } REP (z, 0, 2) { for (int i : rid) { vi p(ALL(lid)); p.pb(i); int s = Query(p) - SZ(p); 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; } } 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; } } 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) { Answer(i, j); } } } }

Compilation message (stderr)

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:102:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |                 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...