[Title Link]
[Points of Thought]
- The following is the author's practice in the examination room, which is different from the standard solution.
- First of all, we can discuss how to use data of A, BA, BA and B.
- For AAA data, each cave is operated with the probability of 12 frac {1} {2} 21. After that, all caves are observed once, and the caves of the same color are grouped into one group, and each type can be processed recursively.
- For BBB class data, we essentially need to calculate the location of the parent node of each node iii. Lighting a prefix, by observing whether node iii is discolored, we can determine whether its father is in a prefix, the whole dichotomy can be.
- For the remaining data, consider the method of imitating AAA data, and operate each cave with the probability of 12 frac {1} {2} 21, and record the set as SSS. After that, we can observe all the caves once. For the discolored cave iiii, we can determine that there are boundaries between iii and odd points in SSS, so there are boundaries between iii and at least one point in SSS. Note that the set of all iii is TTT.
- Operating with the probability of 12 frac {1} {2} 21 for all elements in SSS, SSS can be divided into two sets, one is operated and the other is not operated. Similar to the global dichotomy method for BBB data, it can be determined that there is one side for each element in TTT and at least one point in a set by asking whether it is discolored.
- Moreover, whenever we find an edge, we can delete the new soliton to avoid it appearing in subsequent calculations.
- Expected time complexity O(MLogM)O(MLogM)O(MLogM), expected number of operations O(MLogM)O(MLogM)O(MLogM).
[Code]
#include "explore.h" #include<bits/stdc++.h> using namespace std; int n, m; namespace subtask1 { const int MAXN = 505; bool state[MAXN]; void work() { for (int i = 0; i <= n - 1; i++) state[i] = false; for (int i = 0; i <= n - 2; i++) { modify(i); for (int j = i + 1; j <= n - 1; j++) { if (query(j) != state[j]) { report(i, j); state[j] ^= true; } } } } } namespace subtaskA { const int MAXN = 2e5 + 5; int a[MAXN], tmp[MAXN]; bool cmp(int x, int y) { return tmp[x] < tmp[y]; } void work(int l, int r) { if (l + 1 == r) report(a[l], a[r]); if (r - l + 1 <= 2) return; random_shuffle(a + l, a + r + 1); for (int i = l; i <= r; i++) if (rand() & 1) modify(a[i]); for (int i = l; i <= r; i++) tmp[a[i]] = query(a[i]); sort(a + l, a + r + 1, cmp); int mid = l - 1; for (int i = l; i <= r; i++) if (tmp[a[i]] == 0) mid = i; work(l, mid); work(mid + 1, r); } void work() { srand('X' + 'Y' + 'X'); for (int i = 0; i <= n - 1; i++) a[i] = i; work(0, n - 1); } } namespace subtaskB { const int MAXN = 2e5 + 5; int a[MAXN], tmp[MAXN], cur; bool cmp(int x, int y) { return tmp[x] < tmp[y]; } void work(int l, int r, int ql, int qr) { if (ql > qr) return; if (l == r) { for (int i = ql; i <= qr; i++) report(a[i], l); return; } int mid = (l + r) / 2; while (cur < mid) modify(++cur); while (cur > mid) modify(cur--); for (int i = ql; i <= qr; i++) if (a[i] <= mid || query(a[i])) tmp[a[i]] = false; else tmp[a[i]] = true; sort(a + ql, a + qr + 1, cmp); int qmid = ql - 1; for (int i = ql; i <= qr; i++) if (tmp[a[i]] == false) qmid = i; work(l, mid, ql, qmid); work(mid + 1, r, qmid + 1, qr); } void work() { for (int i = 1; i <= n - 1; i++) a[i] = i; cur = -1, work(0, n - 1, 1, n - 1); } } namespace subtaskF { const int MAXN = 2e5 + 5; bool done[MAXN], state[MAXN]; int cm, cq, fm, a[MAXN], b[MAXN]; bool va[MAXN], vb[MAXN]; vector <int> e[MAXN]; set <pair <int, int> > st; vector <pair <int, int> > pend; void found(int x, int y) { if (x > y) swap(x, y); if (st.count(make_pair(x, y))) return; st.insert(make_pair(x, y)); fm++, report(x, y); pend.push_back(make_pair(x, y)); done[x] = check(x); done[y] = check(y); } void mod(int x) { cm++, state[x] ^= true; for (unsigned i = 0; i < e[x].size(); i++) state[e[x][i]] ^= true; modify(x); } int qry(int x) { cq++; return query(x); } bool cmpa(int x, int y) { return va[x] > va[y]; } bool cmpb(int x, int y) { return vb[x] > vb[y]; } void sortA(int l, int r) { while (l <= r) { if (va[a[l]]) l++; else if (!va[a[r]]) r--; else swap(a[l], a[r]); } } void sortB(int l, int r) { while (l <= r) { if (vb[b[l]]) l++; else if (!vb[b[r]]) r--; else swap(b[l], b[r]); } } void workmod(int la, int ra, int lb, int rb) { if (lb > rb) return; if (la == ra) { for (int i = lb; i <= rb; i++) found(a[la], b[i]); return; } random_shuffle(a + la, a + ra + 1); random_shuffle(b + lb, b + rb + 1); for (int i = la; i <= ra; i++) if (rand() & 1) mod(a[i]), va[a[i]] = true; else va[a[i]] = false; sortA(la, ra); for (int i = lb; i <= rb; i++) if (qry(b[i]) != state[b[i]]) vb[b[i]] = true; else vb[b[i]] = false; sortB(lb, rb); int mida = la - 1, midb = lb - 1; for (int i = la; i <= ra; i++) if (va[a[i]]) mida = i, mod(a[i]); for (int i = lb; i <= rb; i++) if (vb[b[i]]) midb = i; workmod(la, mida, lb, midb); workmod(mida + 1, ra, midb + 1, rb); } void workqry(int la, int ra, int lb, int rb) { if (lb > rb) return; if (la == ra) { for (int i = lb; i <= rb; i++) found(a[la], b[i]); return; } for (int i = lb; i <= rb; i++) state[b[i]] = qry(b[i]); random_shuffle(a + la, a + ra + 1); random_shuffle(b + lb, b + rb + 1); for (int i = la; i <= ra; i++) if (rand() & 1) mod(a[i]), va[a[i]] = true; else va[a[i]] = false; sortA(la, ra); for (int i = lb; i <= rb; i++) if (qry(b[i]) != state[b[i]]) vb[b[i]] = true; else vb[b[i]] = false; sortB(lb, rb); int mida = la - 1, midb = lb - 1; for (int i = la; i <= ra; i++) if (va[a[i]]) mida = i; for (int i = lb; i <= rb; i++) if (vb[b[i]]) midb = i; workqry(la, mida, lb, midb); workqry(mida + 1, ra, midb + 1, rb); } void work() { srand('X' + 'Y' + 'X'); while (fm < m) { for (unsigned i = 0; i < pend.size(); i++) { int x = pend[i].first, y = pend[i].second; e[x].push_back(y); e[y].push_back(x); } pend.clear(); if (cm <= cq) { int la = 0, lb = 0; for (int i = 0; i <= n - 1; i++) if (!done[i] && rand() % 2) a[++la] = i, mod(i); for (int i = 0; i <= n - 1; i++) if (!done[i] && qry(i) != state[i]) b[++lb] = i; for (int i = 1; i <= la; i++) mod(a[i]); workmod(1, la, 1, lb); } else { int la = 0, lb = 0; for (int i = 0; i <= n - 1; i++) if (!done[i] && rand() % 2) a[++la] = i, mod(i); for (int i = 0; i <= n - 1; i++) if (!done[i] && qry(i) != state[i]) b[++lb] = i; workqry(1, la, 1, lb); for (int i = 0; i <= n - 1; i++) if (!done[i]) state[i] = qry(i); } } } } void explore(int N, int M) { n = N, m = M; if (n <= 500) { subtask1 :: work(); return; } else if (N % 10 == 8) { subtaskA :: work(); return; } else if (N % 10 == 7) { subtaskB :: work(); return; } else { subtaskF :: work(); return; } }