oj.uz

Submission #147200

# Submission time Handle Problem Language Result Execution time Memory
147200 2019-08-28T11:46:36 Z karma Carnival (CEOI14_carnival) C++11
100 / 100
 18 ms 404 KB 
#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);
     set<int> irene;
     for(int i = l; i <= mid; ++i) {
        int x = Find(i);
        if(irene.find(x) == irene.end()) UNION(i, mid + 1, r), irene.insert(x);
     }
}

int main()
{
    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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 376 KB Output is correct
2 Correct 16 ms 376 KB Output is correct
3 Correct 12 ms 376 KB Output is correct
4 Correct 10 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 6 ms 404 KB Output is correct
7 Correct 17 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 376 KB Output is correct
2 Correct 18 ms 376 KB Output is correct
3 Correct 9 ms 284 KB Output is correct
4 Correct 7 ms 320 KB Output is correct
5 Correct 8 ms 248 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 14 ms 248 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 248 KB Output is correct
2 Correct 13 ms 248 KB Output is correct
3 Correct 14 ms 316 KB Output is correct
4 Correct 11 ms 248 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 9 ms 248 KB Output is correct
7 Correct 16 ms 248 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 248 KB Output is correct
2 Correct 13 ms 376 KB Output is correct
3 Correct 11 ms 248 KB Output is correct
4 Correct 12 ms 396 KB Output is correct
5 Correct 11 ms 376 KB Output is correct
6 Correct 6 ms 312 KB Output is correct
7 Correct 9 ms 312 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 15 ms 248 KB Output is correct
3 Correct 8 ms 312 KB Output is correct
4 Correct 8 ms 312 KB Output is correct
5 Correct 6 ms 404 KB Output is correct
6 Correct 11 ms 248 KB Output is correct
7 Correct 7 ms 316 KB Output is correct