oj.uz

Submission #280543

# Submission time Handle Problem Language Result Execution time Memory
280543 2020-08-22T22:09:34 Z DS007 Carnival (CEOI14_carnival) C++14
0 / 100
 10 ms 640 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 150;
int n, done[N], ans[N], ans_[N];
vector<int> lef, to_remove;

int query(int v, int l, int r) {
    cout << r - l + 2 << " " << v + 1 << " ";
    for (int i = l; i <= r; i++) cout << lef[i] + 1 << " ";
    cout << endl;

    int val;
    cin >> val;
    return val;
}

void find(int v, int l, int r) {
    if (l == r) {
        int temp = query(v, l, r);
        if (temp == 1)
            to_remove.push_back(lef[l]), ans[lef[l]] = v;
        return;
    }

    if(l > r || r > lef.size())
        exit(0);
    int mid = (l + r) / 2;
    int v1 = query(v, l, mid), v2 = query(v, mid + 1, r);

    if (v1 == 1) {
        for (int i = l; i <= mid; i++)
            to_remove.push_back(lef[i]), ans[lef[i]] = v;
    } else if (v1 != mid - l + 2) {
        find(v, l, mid);
    }

    if (v2 == 1) {
        for (int i = mid + 1; i <= r; i++)
            to_remove.push_back(lef[i]), ans[lef[i]] = v;
    } else if (v2 != r - mid + 1) {
        find(v, mid + 1, r);
    }
}

int solveTestCase() {
    cin >> n;
    for (int i = 0; i < n; i++) lef.push_back(i);

    while (lef.size() >= 1) {
        int v = lef[0];
        if (lef.size() != 1)
            find(v, 1, lef.size() - 1);
        ans[v] = v;
        to_remove.push_back(v);

        for (int i : to_remove)
            lef.erase(remove(lef.begin(), lef.end(), i), lef.end());
        to_remove.clear();
    }

    cout << "0 ";
    for (int i = 0, c = 1; i < n; i++, c++) {
        if (done[i]) {
            c--;
            continue;
        }

        for (int j = i + 1; j < n; j++) {
            if (ans[j] == ans[i])
                ans_[j] = c, done[j] = 1;
        }

        ans_[i] = c;
        done[i] = 1;
    }

    for (int i = 0; i < n; i++)
        cout << ans_[i] << " ";
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    //cin >> test;
    while (test--)
        solveTestCase();
}

Compilation message

carnival.cpp: In function 'void find(long long int, long long int, long long int)':
carnival.cpp:27:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if(l > r || r > lef.size())
      |                 ~~^~~~~~~~~~~~
carnival.cpp: In function 'long long int solveTestCase()':
carnival.cpp:82:1: warning: no return statement in function returning non-void [-Wreturn-type]
   82 | }
      | ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -