Submission #1309417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309417		ofoz	Xoractive (IZhO19_xoractive)	C++20	6 / 100	8 ms	824 KiB

Xoractive

#include <bits/stdc++.h>
#include "interactive.h"
using namespace std;
#define ll long long
#define double long double
#define vc vector<char>
#define vi vector<int>
#define vii vector<vi>
#define viii vector<vii>
#define viiii vector<viii>
#define viiiii vector<viiii>
#define vb vector<bool>
#define pi pair<double, double>
#define ppi pair<pair<int, int>, int>
#define pip pair<int, pair<int, int>>
#define multi multiset<int>
#define multp multiset<pi>
#define endl '\n'      
int a1;

vi exclusion(vi v1, vi v2) {
    if (v1.size() < v2.size()) swap(v1, v2);
    multiset<int> s;
    for (int x : v1) s.insert(x);
    for (int x : v2) s.erase(s.lower_bound(x));
    vi res;
    for (int x : s) res.push_back(x);
    return res;
}

vi intersection(vi v1, vi v2) {
    vi res;
    map<int, int> s2;
    for (int x : v2) s2[x]++;
    for (int x : v1) {
        if (s2[x]) {
            s2[x]--;
            res.push_back(x);
        }
    }
    return res;
}

vi query(vi rng) {
    rng.push_back(1);
    vi q1 = get_pairwise_xor(rng);
    rng.pop_back();
    vi q2 = get_pairwise_xor(rng);
    set<int> s;
    vi res;
    for (int x : exclusion(q1, q2)) {
        if (s.count(x) || !x) continue;
        res.push_back(x);
        s.insert(x);
    }
    return res;
}

vi guess(int n) {
    a1 = ask(1);
    vi rngTot;
    for (int i = 2; i <= n; i++) rngTot.push_back(i);
    vi tot = query(rngTot);
    vii arr;
    vector<pip> seg = {make_pair(0, make_pair(2, n))};
    vii pos(n+1);
    for (int i = 2; i <= n; i++) {
        for (int j : tot) pos[i].push_back(j);
    }
    for (int i = 0; i < 6; i++) {
        vector<pip> nwSeg;
        for (pip p : seg) {
            int m = (p.second.first + p.second.second)/2;
            nwSeg.push_back({0, make_pair(p.second.first, m)});
            if (p.second.first != p.second.second) nwSeg.push_back({1, make_pair(m+1, p.second.second)});
        }
        vi rng;
        for (pip p : nwSeg) {
            if (p.first) continue;
            for (int i = p.second.first; i <= p.second.second; i++) rng.push_back(i);
        }
        vi p1 = query(rng), p2 = exclusion(tot, p1);
        seg = nwSeg;
        for (pip p : nwSeg) {
            for (int i = p.second.first; i <= p.second.second; i++) {
                if (!p.first) pos[i] = intersection(pos[i], p1);
                else pos[i] = intersection(pos[i], p2);
            }
        }
        
    }


    vi res;
    res.push_back(a1);
    for (int i = 2; i <= n; i++) {
        res.push_back(pos[i][0] ^ a1);
    }
    return res;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 94