Hugging Face's logo

JustinTX
/
shinka-backup

Model card Files
xet
 Community
shinka-backup
File size: 3,293 Bytes
14c9c2b
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>
#include <charconv>
using namespace std;

static inline void appendInt(string &s, int x) {
    char buf[16];
    auto [ptr, ec] = std::to_chars(buf, buf + 16, x);
    s.append(buf, ptr);
}

struct Interactor {
    int n;
    long long queries = 0;

    explicit Interactor(int n_) : n(n_) {}

    int ask(const vector<int> &a) {
        ++queries;
        string s;
        s.reserve(4 + n * 5);
        s.push_back('0');
        s.push_back(' ');
        for (int i = 0; i < n; i++) {
            appendInt(s, a[i]);
            s.push_back(i + 1 == n ? '\n' : ' ');
        }
        cout.write(s.data(), (streamsize)s.size());
        cout.flush();

        int x;
        if (!(cin >> x)) exit(0);
        if (x == -1) exit(0);
        return x;
    }

    [[noreturn]] void answer(const vector<int> &p) {
        string s;
        s.reserve(4 + n * 5);
        s.push_back('1');
        s.push_back(' ');
        for (int i = 0; i < n; i++) {
            appendInt(s, p[i]);
            s.push_back(i + 1 == n ? '\n' : ' ');
        }
        cout.write(s.data(), (streamsize)s.size());
        cout.flush();
        exit(0);
    }
};

static inline int ceil_log2_int(int x) {
    int k = 0;
    int p = 1;
    while (p < x) {
        p <<= 1;
        k++;
    }
    return k;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    Interactor it(n);

    if (n == 1) {
        it.answer(vector<int>{1});
    }

    long long searchQueries = 0;
    for (int m = 1; m <= n; m++) searchQueries += ceil_log2_int(m);

    long long budgetForDerangement = 9999 - searchQueries;
    if (budgetForDerangement < 1) budgetForDerangement = 1;
    int maxTries = (int)min<long long>(1000, budgetForDerangement);

    mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
    vector<int> base(n);
    iota(base.begin(), base.end(), 1);

    vector<int> q0;
    bool found = false;

    for (int t = 0; t < maxTries; t++) {
        shuffle(base.begin(), base.end(), rng);
        int x = it.ask(base);
        if (x == 0) {
            q0 = base;
            found = true;
            break;
        }
    }
    if (!found) {
        // Extremely unlikely; keep trying (may exceed the scoring baseline, but preserves correctness)
        for (int t = maxTries; t < 5000; t++) {
            shuffle(base.begin(), base.end(), rng);
            int x = it.ask(base);
            if (x == 0) {
                q0 = base;
                found = true;
                break;
            }
        }
    }
    if (!found) exit(0);

    vector<int> rem(n);
    iota(rem.begin(), rem.end(), 0);
    vector<int> ans(n, 0);

    for (int v = 1; v <= n; v++) {
        int m = (int)rem.size();
        if (m == 1) {
            ans[rem[0]] = v;
            rem.clear();
            break;
        }

        int l = 0, r = m;
        while (r - l > 1) {
            int mid = (l + r) >> 1;
            vector<int> q = q0;
            for (int idx = l; idx < mid; idx++) q[rem[idx]] = v;
            int x = it.ask(q);
            if (x == 1) r = mid;
            else l = mid;
        }
        int pos = rem[l];
        ans[pos] = v;
        rem.erase(rem.begin() + l);
    }

    it.answer(ans);
}