oj.uz

Submission #707729

# Submission time Handle Problem Language Result Execution time Memory
707729 2023-03-09T22:04:07 Z ktkerem Carnival (CEOI14_carnival) C++17
100 / 100
 12 ms 328 KB 
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;
const ll limit = 1e18+7;
const ll sus = 150 + 5;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll a , ll b){
    return (rng() % (b-a+1)) + a;
}
/*global variables*/
ll n;
ll par[sus] , sz[sus];
/**/
/*functions*/
ll fin(ll x){
    if(par[x] == x){
        return x;
    }
    return par[x] = fin(par[x]);
}
ll mrg(ll a , ll b){
    a = fin(a);b = fin(b);
    if(a == b){
        return 0;
    }
    if(sz[a] < sz[b]){
        std::swap(a , b);
    }
    par[b] = a;
    sz[a] += sz[b];
    return 1;
}
std::vector<ll> fun(ll l , ll r){
    //std::cout << l << " " << r << std::endl;
    if(l == r){
        return std::vector<ll>{l}; 
    }
    ll md = (l + r) / 2;
    std::vector<ll> lf = fun(l , md);
    std::vector<ll> rs = fun(md+1 , r);
    std::vector<ll> kd(rs.size() , 1);
    for(ll i = 0;lf.size()>i;i++){
        std::queue<llll> qu;qu.push({0 , rs.size()-1});
        while(!qu.empty()){
            llll a = qu.front();qu.pop();
            std::cout << 1 + (a.sec - a.fi + 1) << " "  << lf[i] << " ";
            for(ll j = a.fi;a.sec >= j;j++){
                std::cout << rs[j] << " ";
            }
            std::cout << std::endl;
            ll o;std::cin >> o;
            ll md = (a.fi + a.sec)/2;
            if(o < 1 + (a.sec - a.fi + 1)){
                if(a.fi == a.sec){
                    mrg(lf[i] , rs[a.sec]);
                    kd[a.sec] = 0;
                    continue;
                }
                qu.push( {a.fi , md});
                qu.push({md+1,a.sec});
            }
        }
    }
    for(ll i = 0;rs.size()>i;i++){
        if(kd[i]){
            lf.pb(rs[i]);
        }
    }
    return lf;
}
/**/
void solve(){
    std::cin >> n;
    for(ll i = 0;n>=i;i++){
        par[i] = i;
        sz[i] = 1;
    }
    fun(1 , n);
    ll x = 1;
    std::map<ll , ll> mp;
    std::cout << 0 << " ";
    for(ll i = 1;n>=i;i++){
        if(mp[fin(i)] == 0){
            mp[fin(i)] = x++; 
        }
        std::cout << mp[fin(i)] << " "; 
    }
    std::cout << std::endl;
    return;/**/
}
int main(){
    //std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
    /*#ifndef ONLINE_JUDGE
        freopen("in.txt" , "r" , stdin);
        freopen("out.txt" , "w" , stdout);
    #endif*/
    ll t = 1;
    //std::cin >> t;
    while(t--){
        solve();
    }
}

Compilation message

carnival.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |                                                                               
carnival.cpp: In function 'std::vector<long long int> fun(ll, ll)':
carnival.cpp:53:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   53 |     for(ll i = 0;lf.size()>i;i++){
      |                  ~~~~~~~~~^~
carnival.cpp:75:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   75 |     for(ll i = 0;rs.size()>i;i++){
      |                  ~~~~~~~~~^~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Output is correct
2 Correct 10 ms 208 KB Output is correct
3 Correct 11 ms 292 KB Output is correct
4 Correct 7 ms 312 KB Output is correct
5 Correct 7 ms 208 KB Output is correct
6 Correct 5 ms 308 KB Output is correct
7 Correct 12 ms 312 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 7 ms 208 KB Output is correct
3 Correct 9 ms 308 KB Output is correct
4 Correct 5 ms 312 KB Output is correct
5 Correct 6 ms 208 KB Output is correct
6 Correct 4 ms 312 KB Output is correct
7 Correct 10 ms 304 KB Output is correct

Subtask #5
20.0 / 20.0

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