oj.uz

Submission #1092373

# Submission time Handle Problem Language Result Execution time Memory
1092373 2024-09-24T00:11:20 Z vjudge1 Carnival (CEOI14_carnival) C++17
100 / 100
 10 ms 708 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
 
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
 
// #define endl '\n'
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i,l,r) for(auto i=l;i<r;i++)
#define fo(i,n) fore(i,0,n)
#define forex(i,r,l) for(auto i=r; i>=l;i--)
#define ffo(i,n) forex(i,n-1,0)
 
bool cmin(ll &a, ll b) { if(b<a){a=b;return 1;}return 0; }
bool cmax(ll &a, ll b) { if(b>a){a=b;return 1;}return 0; }
void valid(ll in) { cout<<((in)?"YES\n":"NO\n"); }
ll lcm(ll a, ll b) { return (a/gcd(a,b))*b; }
ll gauss(ll n) { return (n*(n+1))/2; }
 
int query (vi p) {
    cout << sz(p) << ' ';
    for (int v: p) cout << v+1 << ' ';
    cout << endl;
    int ans;
    cin >> ans;
    return ans;
 
}
void test_case() {
    int n;
    cin >> n;
    vi dfs, ans(n, 0);
    dfs.pb(0);
    fore (i, 1, n) {
        int l = 0, r = sz(dfs)-1;
        while (l <= r) {
            int m = (l+r)/2;
            vi p;
            fore (j, m, sz(dfs)) p.pb(dfs[j]);
            p.pb(i);
            int q = query(p);
            if (q == sz(dfs)-m+1) r = m-1;
            else l = m+1;
        }
        if (r < 0) ans[i] = sz(dfs), dfs.pb(i);
        else ans[i] = ans[dfs[r]];
    }
    cout << "0 ";
    for (int v: ans) cout << v+1 << ' ';
}
 
int main(){cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin >> tt;
    while(tt--) test_case();
}

Compilation message

carnival.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
carnival.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

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