제출 #1348456

#제출 시각아이디문제언어결과실행 시간메모리
1348456vain_kane사육제 (CEOI14_carnival)C++17
20 / 100
19 ms416 KiB
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define BIT(i, x) (((x) >> (i)) & 1)
#define MK(i) (1LL << (i))
#define all(v) v.begin(), v.end()
#define sz(v) ((int)v.size())
#define F first
#define S second

template <class t> bool maxi(t &x, t const &y)
{
    return x < y ? x = y, 1 : 0;
}

template <class t> bool mini(t &x, t const &y)
{
    return x > y ? x = y, 1 : 0;
}

int const N = 1e5 + 5;
int const BK = 12;
int const GR = N / BK + 5;

int bkId[N], bkL[N], bkR[N];
int sz[GR];

int n;
int c[N];
int cnt = 0;

void Init()
{
    FOR(i, 1, n)
    {
        int id = (i - 1) / BK + 1;
        if (!bkL[id]) bkL[id] = i;
        bkR[id] = i;
    }
}

int Query(vector<int> v)
{
    cout << sz(v) << ' ';
    for (auto &x : v) cout << x << ' ';
    cout << '\n' << flush;

    int res; cin >> res;
    if (res == -1) exit(0);

    return res;
}

void Answer()
{
    cout << "0 ";
    FOR(i, 1, n) cout << c[i] << ' ';
    cout << '\n' << flush;
}

int Find(int l, int r, int pos)
{
    if (bkId[l] == bkId[r])
    {
        FOR(i, l, r) if (Query({i, pos}) == 1) return i;
        return 0;
    }

    FOR(id, bkL[bkId[l]], bkR[bkId[r] - 1])
    {
        vector<int> v = {pos};
        FOR(i, bkL[id], bkR[id]) v.push_back(i);
        if (Query(v) == sz[id]) return Find(bkL[id], bkR[id], pos);
    }

    return Find(bkL[bkId[r]], bkR[bkId[r]], pos);
}

bool Check(int l, int r, int pos)
{
    FOR(i, l, r) if (c[i] == c[pos]) return false;
    return true;
}

int main()
{
    cin >> n;
    Init();

    FOR(i, 1, n)
    {
        int pos = Find(1, i - 1, i);
        c[i] = pos ? c[pos] : ++cnt;

        int id = bkId[i];
        sz[id] += Check(bkL[id], i - 1, i);
    }

    Answer();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...