oj.uz

답안 #147199

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
147199 2019-08-28T11:46:16 Z karma 사육제 (CEOI14_carnival) C++11
0 / 100
 3 ms 376 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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 248 KB Integer 12 violates the range [1, 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 248 KB Integer 6 violates the range [1, 5
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Integer 2 violates the range [1, 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 312 KB Integer 5 violates the range [1, 4
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 248 KB Integer 3 violates the range [1, 2
2 Halted 0 ms 0 KB -