Submission #147198

#	Time	Username	Problem	Language	Result	Execution time	Memory
147198		karma	Carnival (CEOI14_carnival)	C++11	100 / 100	31 ms	424 KiB

carnival

#include <bits/stdc++.h>
#pragma GCC optimization ("O3")

using namespace std;

const int N = 157;

static int lab[N], ans[N], n, cnt;
set<int> s;

int Find(int u)
{
    return lab[u] < 0? u: lab[u] = Find(lab[u]);
}

void Union(int u, int v)
{
     int s = Find(u), r = Find(v);
     if(s == r) return;
     if(lab[r] > lab[s]) swap(r, s);
     lab[r] += lab[s];
     lab[s] = r;
}

int ask(int x, int l, int r)
{
    int len = (x != -1) + r - l + 1;
    cout << len << ' ';
    for(int i = l; i <= r; ++i) cout << i + 1 << ' ';
    if(x != -1) cout << x + 1 << ' ';
    cout << '\n';
    cin >> len;
    return len;
}

int GetAns(int l, int r)
{
    s.clear();
    for(int i = l; i <= r; ++i) s.insert(Find(i));
    return int(s.size());
}

void UNION(int x, int lef, int rig)
{
    if(ask(x, lef, rig) != GetAns(lef, rig)) return;
    int l = lef, h = rig, mid, cc;
    while(l < h) {
        mid = (l + h) >> 1;
        cc = ask(x, l, mid);
        if(cc == GetAns(l, mid)) h = mid;
        else l = mid + 1;
    }
    Union(x, l);
}

void Divide(int l, int r)
{
     if(l >= r) return;
     if(r - l == 1) {
        int cc = ask(-1, l, r);
        if(cc == 1) Union(l, r);
        return;
     }
     int mid = (l + r) >> 1;
     Divide(l, mid); Divide(mid + 1, r);
     for(int i = l; i <= mid; ++i) UNION(i, mid + 1, r);
}

int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0), cout.tie(0);
    cin >> n;
    memset(&lab, -1, sizeof lab);
    Divide(0, n - 1);
    for(int i = 0; i < n; ++i) s.insert(Find(i));
    for(int x: s) ans[x] = ++cnt;
    cout << "0 ";
    for(int i = 0; i < n; ++i) cout << ans[Find(i)] << ' ';
}

Compilation message (stderr)

carnival.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20