Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup / docker_space /frontier_cs_3 /solution_v3.cpp
JustinTX's picture
JustinTX
Add files using upload-large-folder tool
1fd0050 verified
Raw History Blame Contribute Delete
12.1 kB
#include <bits/stdc++.h>
using namespace std;
static int N;
static inline int readInt() {
int c = getchar_unlocked();
while (c != '-' && (c < '0' || c > '9')) {
c = getchar_unlocked();
if (c == EOF) return 0;
}
int sgn = 1;
if (c == '-') { sgn = -1; c = getchar_unlocked(); }
int x = 0;
while (c >= '0' && c <= '9') { x = x*10+(c-'0'); c = getchar_unlocked(); }
return x * sgn;
}
static char wbuf[1 << 23];
static int wpos = 0;
static void wflush() { if (wpos > 0) fwrite(wbuf, 1, wpos, stdout); wpos = 0; fflush(stdout); }
static void wchar(char c) { if (wpos >= (1<<23)-2) wflush(); wbuf[wpos++] = c; }
static void wint(long long x) {
if (x < 0) { wchar('-'); x = -x; }
if (x == 0) { wchar('0'); return; }
char buf[20]; int len = 0;
while (x > 0) { buf[len++] = '0'+(int)(x%10); x /= 10; }
for (int i = len-1; i >= 0; i--) wchar(buf[i]);
}
static int resBuf[10000010];
static void doRound(const vector<int>& ops, int* res) {
wint((int)ops.size());
for (int x : ops) { wchar(' '); wint(x); }
wchar('\n'); wflush();
for (int i = 0; i < (int)ops.size(); i++) res[i] = readInt();
}
static void doRound2(const int* ops, int cnt, int* res) {
wint(cnt);
for (int i = 0; i < cnt; i++) { wchar(' '); wint(ops[i]); }
wchar('\n'); wflush();
for (int i = 0; i < cnt; i++) res[i] = readInt();
}
static void doRoundIgnore(const vector<int>& ops) {
if (ops.empty()) return;
doRound(ops, resBuf);
}
static int toggle1(int v) {
wint(1); wchar(' '); wint(v); wchar('\n'); wflush();
return readInt();
}
static mt19937 rng(42);
static void solve_small() {
vector<int> ops;
vector<pair<int,int>> pairs;
for (int i = 1; i <= N; i++)
for (int j = i+1; j <= N; j++) {
ops.push_back(i); ops.push_back(j);
ops.push_back(i); ops.push_back(j);
pairs.push_back({i,j});
}
doRound(ops, resBuf);
vector<vector<int>> adj(N+1);
for (size_t k = 0; k < pairs.size(); k++)
if (resBuf[4*k+1] == 1) {
adj[pairs[k].first].push_back(pairs[k].second);
adj[pairs[k].second].push_back(pairs[k].first);
}
vector<int> chain = {1};
if (N > 1 && !adj[1].empty()) {
chain.push_back(adj[1][0]);
for (int i = 2; i < N; i++) {
int last = chain.back(), prev = chain[chain.size()-2];
for (int nb : adj[last])
if (nb != prev) { chain.push_back(nb); break; }
}
}
wint(-1);
for (int v : chain) { wchar(' '); wint(v); }
wchar('\n'); wflush();
}
// Build IS using batch toggle approach
// Precondition: S is empty
// Postcondition: S = returned IS nodes (all toggled on)
static vector<int> buildIS_batch(vector<int> nodes) {
if (nodes.empty()) return {};
shuffle(nodes.begin(), nodes.end(), rng);
set<int> isSet;
vector<int> IS;
// Phase: Toggle all, find IS prefix, remove rest
// Repeat with remaining candidates that aren't adjacent to IS
vector<int> candidates = nodes;
for (int iter = 0; iter < 300 && !candidates.empty(); iter++) {
shuffle(candidates.begin(), candidates.end(), rng);
// Round 1: toggle all candidates
doRound(candidates, resBuf);
int j = (int)candidates.size();
for (int i = 0; i < (int)candidates.size(); i++) {
if (resBuf[i] == 1) { j = i; break; }
}
for (int i = 0; i < j; i++) {
IS.push_back(candidates[i]);
isSet.insert(candidates[i]);
}
// Round 2: toggle off non-IS candidates
if (j < (int)candidates.size()) {
vector<int> rem;
for (int i = (int)candidates.size()-1; i >= j; i--)
rem.push_back(candidates[i]);
doRoundIgnore(rem);
}
if (j == (int)candidates.size()) break;
// Filter: probe each remaining candidate against IS
vector<int> remaining;
for (int v : candidates) if (!isSet.count(v)) remaining.push_back(v);
if (remaining.empty()) break;
{
vector<int> ops;
ops.reserve(2 * remaining.size());
for (int v : remaining) { ops.push_back(v); ops.push_back(v); }
doRound(ops, resBuf);
}
candidates.clear();
for (int i = 0; i < (int)remaining.size(); i++) {
if (resBuf[2*i] == 0) candidates.push_back(remaining[i]);
}
}
return IS;
}
// Clear S: toggle off all IS nodes
static void clearS(const vector<int>& IS, vector<bool>& curLit) {
vector<int> ops;
for (int i = 0; i < (int)IS.size(); i++)
if (curLit[i]) { ops.push_back(IS[i]); curLit[i] = false; }
if (!ops.empty()) doRoundIgnore(ops);
}
static void solve_large() {
vector<int> allNodes(N);
iota(allNodes.begin(), allNodes.end(), 1);
// Phase 1: Build maximal IS using batch approach
vector<int> IS = buildIS_batch(allNodes);
int m = (int)IS.size();
// Debug: output IS size to stderr
// fprintf(stderr, "IS size: %d / %d\n", m, N);
vector<bool> inIS(N+1, false);
for (int v : IS) inIS[v] = true;
vector<int> nonIS;
for (int v = 1; v <= N; v++) if (!inIS[v]) nonIS.push_back(v);
int nm = (int)nonIS.size();
// Phase 2: Identify IS-neighbors using sum + sum-of-squares
// Each non-IS node has exactly 2 neighbors in the ring. Some of those neighbors
// are in IS, some are not.
// - If both neighbors are in IS: need sum and sq to identify them
// - If one neighbor is in IS: need sum to identify it (sq not needed, but helps)
// - If no neighbors are in IS: won't be found in this phase
int bits_sum = 0;
{ int v = 2*m; while (v > 0) { bits_sum++; v >>= 1; } }
bits_sum = max(bits_sum, 1);
int bits_sq = 0;
{ long long v = 2LL*m*m; while (v > 0) { bits_sq++; v >>= 1; } }
bits_sq = max(bits_sq, 1);
vector<long long> labsq(m);
for (int i = 0; i < m; i++) labsq[i] = (long long)(i+1)*(i+1);
vector<bool> curLit(m, true);
vector<long long> nsum(nm, 0), nsq(nm, 0);
vector<int> carry_s(nm, 0), carry_q(nm, 0);
int maxBits = max(bits_sum, bits_sq);
for (int b = 0; b < maxBits; b++) {
if (b < bits_sum) {
vector<int> ops;
ops.reserve(3*m + 4*nm);
for (int i = 0; i < m; i++) {
bool want = (((i+1)>>b)&1)==1;
if (curLit[i] != want) { ops.push_back(IS[i]); curLit[i] = want; }
}
int po1 = (int)ops.size();
for (int v : nonIS) { ops.push_back(v); ops.push_back(v); }
for (int i = 0; i < m; i++) {
bool want = (((i+1)>>b)&1)==0;
if (curLit[i] != want) { ops.push_back(IS[i]); curLit[i] = want; }
}
int po2 = (int)ops.size();
for (int v : nonIS) { ops.push_back(v); ops.push_back(v); }
doRound(ops, resBuf);
for (int j = 0; j < nm; j++) {
int ho = resBuf[po1+2*j];
int hz = resBuf[po2+2*j];
int cnt = !ho ? 0 : !hz ? 2 : 1;
int total = cnt + carry_s[j];
if (total & 1) nsum[j] |= (1LL << b);
carry_s[j] = total >> 1;
}
}
if (b < bits_sq) {
vector<int> ops;
ops.reserve(3*m + 4*nm);
for (int i = 0; i < m; i++) {
bool want = ((labsq[i]>>b)&1)==1;
if (curLit[i] != want) { ops.push_back(IS[i]); curLit[i] = want; }
}
int po1 = (int)ops.size();
for (int v : nonIS) { ops.push_back(v); ops.push_back(v); }
for (int i = 0; i < m; i++) {
bool want = ((labsq[i]>>b)&1)==0;
if (curLit[i] != want) { ops.push_back(IS[i]); curLit[i] = want; }
}
int po2 = (int)ops.size();
for (int v : nonIS) { ops.push_back(v); ops.push_back(v); }
doRound(ops, resBuf);
for (int j = 0; j < nm; j++) {
int ho = resBuf[po1+2*j], hz = resBuf[po2+2*j];
int cnt = !ho ? 0 : !hz ? 2 : 1;
int total = cnt + carry_q[j];
if (total & 1) nsq[j] |= (1LL << b);
carry_q[j] = total >> 1;
}
}
}
for (int j = 0; j < nm; j++) {
if (carry_s[j]) nsum[j] |= ((long long)carry_s[j] << bits_sum);
if (carry_q[j]) nsq[j] |= ((long long)carry_q[j] << bits_sq);
}
// Phase 3: Reconstruct edges
vector<array<int,2>> adj(N+1, {0,0});
vector<int> deg(N+1, 0);
auto addEdge = [&](int u, int v) {
if (u == v || u < 1 || u > N || v < 1 || v > N) return;
if (deg[u] >= 2 || deg[v] >= 2) return;
for (int k = 0; k < deg[u]; k++) if (adj[u][k] == v) return;
adj[u][deg[u]++] = v;
adj[v][deg[v]++] = u;
};
for (int j = 0; j < nm; j++) {
long long S1 = nsum[j], S2 = nsq[j];
if (S1 == 0 && S2 == 0) continue;
long long disc = 2*S2 - S1*S1;
if (disc < 0) continue;
long long d = (long long)round(sqrt((double)disc));
while (d > 0 && d*d > disc) d--;
while ((d+1)*(d+1) <= disc) d++;
if (d*d != disc) continue;
if ((S1+d)%2 != 0) continue;
long long la = (S1+d)/2, lb = (S1-d)/2;
if (la >= 1 && la <= m) addEdge(nonIS[j], IS[la-1]);
if (lb >= 1 && lb <= m && lb != la) addEdge(nonIS[j], IS[lb-1]);
}
// Phase 4: Handle nodes with deg < 2
{
vector<int> clearOps;
for (int i = 0; i < m; i++)
if (curLit[i]) { clearOps.push_back(IS[i]); curLit[i] = false; }
if (!clearOps.empty()) doRoundIgnore(clearOps);
}
vector<int> deg1;
for (int v : nonIS) if (deg[v] < 2) deg1.push_back(v);
if (!deg1.empty()) {
vector<int> IS2 = buildIS_batch(deg1);
int m2 = (int)IS2.size();
set<int> is2Set(IS2.begin(), IS2.end());
vector<int> nonIS2;
for (int v : deg1) if (!is2Set.count(v)) nonIS2.push_back(v);
int nm2 = (int)nonIS2.size();
if (m2 > 0 && nm2 > 0) {
vector<bool> curLit2(m2, true);
int bits2 = 0;
{ int v = m2; while (v > 0) { bits2++; v >>= 1; } }
bits2 = max(bits2, 1);
vector<int> nsum2(nm2, 0);
for (int b = 0; b < bits2; b++) {
vector<int> ops;
ops.reserve(m2 + 2*nm2);
for (int i = 0; i < m2; i++) {
bool want = (((i+1)>>b)&1)==1;
if (curLit2[i] != want) { ops.push_back(IS2[i]); curLit2[i] = want; }
}
int po = (int)ops.size();
for (int v : nonIS2) { ops.push_back(v); ops.push_back(v); }
doRound(ops, resBuf);
for (int j = 0; j < nm2; j++)
if (resBuf[po+2*j]==1) nsum2[j] |= (1<<b);
}
for (int j = 0; j < nm2; j++) {
int label = nsum2[j];
if (label >= 1 && label <= m2) addEdge(nonIS2[j], IS2[label-1]);
}
}
}
// Traverse ring
vector<int> order;
order.reserve(N);
int start = 1;
for (int v = 1; v <= N; v++) if (deg[v] == 2) { start = v; break; }
int prev = 0, cur = start;
for (int i = 0; i < N; i++) {
order.push_back(cur);
int nxt = (adj[cur][0] != prev) ? adj[cur][0] : adj[cur][1];
prev = cur; cur = nxt;
if (cur == 0 || cur == start) break;
}
if ((int)order.size() != N) {
order.clear();
for (int v = 1; v <= N; v++) order.push_back(v);
}
wint(-1);
for (int v : order) { wchar(' '); wint(v); }
wchar('\n'); wflush();
}
int main() {
int subtask = readInt();
N = readInt();
if (N <= 1) { wint(-1); wchar(' '); wint(1); wchar('\n'); wflush(); return 0; }
if (N <= 1500) solve_small();
else solve_large();
return 0;
}