oj.uz

Submission #469849

# Submission time Handle Problem Language Result Execution time Memory
469849 2021-09-02T05:54:34 Z PancakeFactory Carnival (CEOI14_carnival) C++14
100 / 100
 10 ms 200 KB 
#include <bits/stdc++.h>
using namespace std;
/* ################################ */
#define pb push_back
#define FOR(i, a, n) for(int i = (a); i < (n); i++)
#define FORN(i, n) for(int i = 0; i < (n); i++)
#define SZ(x) ((int) (x).size())
#define mp(x,y) make_pair((x), (y))
#define xx first
#define yy second
#define clr clear()
#define MOD 1000000007
typedef long long ll;
/* ################################ */
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wsizeof-array-argument"
template<typename T>void dbg_var(T data){cout<<data<<endl;};
void dbg_vec(const vector<int>& v){FOR(i,0,(int)v.size()){cout<<v[i]<<" ";}cout<<endl;}
void dbg_varlist(const vector<pair<string, int>>& s){FOR(i, 0, (int)s.size()){cout<<s[i].first<<": "<<s[i].second<<" | ";}cout<<endl;}
template <class T, unsigned N> void dbg_arr(T (&arr)[N]){int size = sizeof(arr)/sizeof(arr[0]);FOR(i,0,size){cout<<arr[i]<<" ";}cout<<endl;}
#pragma GCC diagnostic pop
/* ################################ */

int costWorn[151] = {0};
int ans[151] = {0};

int query(int l, int r, int x) {
    cout << (r-l)+2 << " ";
    FOR(i, l, r+1) cout << costWorn[i] << " ";
    cout << x << endl;

    cin >> x;
    return x;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;

    int costSeen = 1;
    costWorn[1] = 1;
    ans[1] = 1;

    FOR(i, 2, n+1) {

        if(query(1, costSeen, i) > costSeen) {
            costSeen++;
            ans[i] = costSeen;
            costWorn[costSeen] = i;

        } else {
            int low = 1, high = costSeen;
            while(low < high) {
                int mid = (low+high) >> 1;
                
                if(query(low, mid, i) == (mid+1) - low) {
                    high = mid;
                } else {
                    low = mid+1;
                }
            }

            ans[i] = ans[costWorn[low]];
        }
    }

    cout << 0 << " ";
    FOR(i, 1, n+1) cout << ans[i] << " ";
    cout << endl;

    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

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