oj.uz

Submission #245641

# Submission time Handle Problem Language Result Execution time Memory
245641 2020-07-07T02:58:42 Z generic_placeholder_name Carnival (CEOI14_carnival) C++17
100 / 100
 13 ms 384 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>

#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename _def> using ordered_set=tree<_def, null_type, less<_def>, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

int ask(vi& a, int l=-1, int r=-1, int add=-1) {
    if(l==-1) l=0, r=a.size()-1;
    if(add==-1) cout<<r-l+1<<' '; else cout<<r-l+2<<' ';
    for(int i=l; i<=r; i++) cout<<a[i]<<' ';
    if(add!=-1) cout<<add;
    cout<<endl;
    int resp; cin>>resp; return resp;
}

void answer(vi& ans) {
    for(int it: ans) cout<<it<<' '; cout<<endl;
}

int32_t main() {
    int n; cin>>n;
    vi tops{1}, ans(n+1); ans[1]=1;
    for(int i=2; i<=n; i++) {
        tops.pb(i);
        if(ask(tops)==tops.size()) {
            ans[i]=tops.size();
            continue;
        }
        tops.pop_back();
        int l=0, r=tops.size()-1;
        while(r>l) {
            int m=(r+l)/2;
            if(ask(tops, l, m, i)<m-l+2) r=m;
            else l=m+1;
        }
        ans[i]=l+1;
    }
    answer(ans);
}

Compilation message

carnival.cpp:7:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops, no-stack-protector")
 
carnival.cpp: In function 'void answer(vi&)':
carnival.cpp:54:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int it: ans) cout<<it<<' '; cout<<endl;
     ^~~
carnival.cpp:54:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(int it: ans) cout<<it<<' '; cout<<endl;
                                     ^~~~
carnival.cpp: In function 'int32_t main()':
carnival.cpp:62:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ask(tops)==tops.size()) {
            ~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

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