oj.uz

Submission #752647

# Submission time Handle Problem Language Result Execution time Memory
752647 2023-06-03T11:11:59 Z benjaminkleyn Carnival (CEOI14_carnival) C++17
100 / 100
 10 ms 316 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
bool done[150];
int val[150];

int query(const vector<int> &peoples, int l = 0, int r = 149, int extra = -1)
{
    cout << min((int)peoples.size(), r + 1) - l + (extra != -1);
    for (int i = l; i <= r && i < peoples.size(); i++)
        cout << ' ' << peoples[i] + 1;
    if (extra != -1)
        cout << ' ' << extra + 1;
    cout << '\n';

    cout.flush();
    int result;
    cin >> result;
    return result;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;

    vector<int> a = {0};
    done[0] = true;
    int cur = 1;
    for (int i = 1; i < n; i++)
    {
        a.push_back(i);
        if (query(a) > cur)
            cur++, done[i] = true;
        else
            a.pop_back();
    }

    int c = 0;
    for (int i : a)
        val[i] = c++;

    for (int i = 0; i < n; i++)
        if (!done[i])
        {
            // binary search in a to find the same costume.
            int lo = 0, hi = c - 1, mid;
            while (lo < hi)
            {
                mid = (lo + hi) / 2;
                if (query(a, lo, mid, i) == mid - lo + 1)
                    hi = mid;
                else
                    lo = mid + 1;
            }
            val[i] = val[a[lo]];
        }

    cout << '0';
    for (int i = 0; i < n; i++)
        cout << ' ' << val[i] + 1;
    cout << '\n';

    return 0;
}

Compilation message

carnival.cpp: In function 'int query(const std::vector<int>&, int, int, int)':
carnival.cpp:12:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = l; i <= r && i < peoples.size(); i++)
      |                               ~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 208 KB Output is correct
2 Correct 8 ms 208 KB Output is correct
3 Correct 5 ms 208 KB Output is correct
4 Correct 3 ms 312 KB Output is correct
5 Correct 4 ms 208 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Correct 3 ms 208 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 208 KB Output is correct
2 Correct 9 ms 208 KB Output is correct
3 Correct 5 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
5 Correct 3 ms 208 KB Output is correct
6 Correct 8 ms 208 KB Output is correct
7 Correct 8 ms 208 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 6 ms 208 KB Output is correct
3 Correct 6 ms 208 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 5 ms 208 KB Output is correct
6 Correct 10 ms 208 KB Output is correct
7 Correct 4 ms 208 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 3 ms 208 KB Output is correct
3 Correct 5 ms 208 KB Output is correct
4 Correct 3 ms 316 KB Output is correct
5 Correct 7 ms 208 KB Output is correct
6 Correct 6 ms 208 KB Output is correct
7 Correct 9 ms 208 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 8 ms 208 KB Output is correct
3 Correct 6 ms 208 KB Output is correct
4 Correct 7 ms 208 KB Output is correct
5 Correct 6 ms 208 KB Output is correct
6 Correct 6 ms 208 KB Output is correct
7 Correct 3 ms 208 KB Output is correct