제출 #1309577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309577		ofoz	Xoractive (IZhO19_xoractive)	C++20	100 / 100	7 ms	1120 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) {
    multiset<int> s;
    for (int x : v1) s.insert(x);
    for (int x : v2) {
        if (!s.count(x)) continue;
        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);
    vii arr;
    vector<pip> seg = {make_pair(0, make_pair(2, n))};
    vii pos(n+1), notPos(n+1);
    vector<set<int>> notPosSet(n+1);

    for (int i = 0; i < 7; 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);
        seg = nwSeg;
        for (pip p : nwSeg) {
            for (int i = p.second.first; i <= p.second.second; i++) {
                if (!p.first) {
                    if (pos[i].empty()) pos[i] = p1;
                    else pos[i] = intersection(pos[i], p1);
                }
                else {
                    for (int j : p1) {
                        if (notPosSet[i].count(j)) continue;
                        notPos[i].push_back(j);
                        notPosSet[i].insert(j);
                    }
                }
            }
        }
        
    }
    for (int i = 2; i <= n; i++) {
        // cerr << pos[i].size() << endl;
        pos[i] = exclusion(pos[i], notPos[i]);
    }

    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: 94 / 94