Submission #986692

#	Time	Username	Problem	Language	Result	Execution time	Memory
986692		PurpleCrayon	Ancient Machine 2 (JOI23_ancient2)	C++17	97 / 100	71 ms	1100 KiB

ancient2

#include "ancient2.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;

mt19937 rng(69);

int rnd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}

int qry(vector<int> v) {
    int m = 2 * sz(v);
    vector<int> a(m), b(m);
    for (int i = 0; i < m; i++) {
        int par = i % 2, c = i / 2;
        a[i] = ((c + 1) % sz(v)) * 2 + par;
        if (v[c]) {
            b[i] = ((c + 1) % sz(v)) * 2 + (par ^ 1);
        } else {
            b[i] = a[i];
        }
    }

    return Query(m, a, b) % 2;
}

string Solve(int N) {
    const int p = 57;
    const int n = 1e3;
    assert(n == N);

    bitset<n> b[n]; // basis
    int who[n];
    for (int i = 0; i < n; i++) b[i] = 0;

    int cnt = 0;
    while (cnt < n) {
        int x = rnd(1, p);
        vector<int> use(x);
        for (int i = 0; i < x; i++) use[i] = rnd(0, 1);

        bitset<n> cur;
        int my_who = 0;
        for (int i = 0; i < n; i++) cur[i] = use[i % x];

        for (int i = 0; i < n; i++) if (cur[i]) {
            if (b[i].any()) {
                cur ^= b[i];
                my_who ^= who[i];
            } else {
                b[i] = cur;
                who[i] = my_who ^= qry(use);
                cnt++;
                break;
            }
        }
    }

    string s;
    for (int i = 0; i < n; i++) {
        int ans = 0;

        bitset<n> cur; cur[i] = 1;
        for (int j = 0; j < n; j++) if (cur[j]) {
            cur ^= b[j];
            ans ^= who[j];
        }

        s += char('0' + ans);
    }

    return s;
}

• Subtask 1: 97 / 100