oj.uz

Submission #1044407

# Submission time Handle Problem Language Result Execution time Memory
1044407 2024-08-05T09:24:40 Z hynmj Carnival (CEOI14_carnival) C++17
100 / 100
 4 ms 600 KB 
//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define ll long long
#define ln cout<<endl
#define int long long
#define Code ios_base::sync_with_stdio(0);
#define by cin.tie(NULL);
#define Hayan cout.tie(NULL);
#define append push_back
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define vi vector<int>
#define vs vector<string>
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define vb vector<bool>
#define vv vector<vi>
#define vp vector<pi>
#define vs vector<string>
#define ul map<int,vi>
#define ub map<int,bool>
#define ui map<int,int>
#define sum(a) accumulate(all(a),0)
// #define endl '\n' 
#define pi pair<int,int>
#define ff first
#define ss second
using namespace std;
const int INF=1e18;
int n,k,e,m,ans=0;
vi a,p;
bool comp (pi &a, pi &b)
{
    return a.ss<b.ss;
}
int get(int x)
{
    if (p[x]!=x){p[x]=get(p[x]);}
    return p[x];
}
void union_(ll a,ll b )
{
   ll  a_r=get(a);
   ll  b_r=get(b);
    p[b_r]=a_r;
}
bool q (int x)
{
    cout<<a.size()+1<<" ";
    for (auto i: a)
        cout<<i<<" ";cout<<x<<" ";cout<<endl;
    cin>>e;
    return a.size()!=e;
}
int greed(int x,int l=0,int r=a.size())
{
    if (r-l==1)
        return a[l];
    int mid=(r+l)/2;
    cout<<mid-l+1<<" ";
    cout<<x<<" ";
    for (int i=l; i < mid; i++)
        cout<< a[i] << " ";ln;
    cin>>e;
    if (e==mid-l)
    {
        return greed(x,l,mid);
    }
    else 
    {
        return greed(x,mid,r);
    }
}
void solve()
{
    a.append(1);
    cin>>n;
    rep(n+1)p.append(i);
    for (int i=2;i<=n;i++)
    {
        if (q(i))
        {
            a.append(i);continue;
        }
        int x=greed(i);
        union_(x,i);
        // cout<<endl<<"taking union of  "<<x<<" "<<i<<endl;ln;
    }
    cout<<0<< " ";
    
    set<int> an;        
    for (int i=1;i<=n;i++)
    {
        an.insert(get(i));
    }
    int j=0;
    ui mp;
    for (int i:an)
    {
        mp[i]=++j;
    }
    for (int i=1;i<=n;i++)
    {
        cout<<mp[get(i)]<<" ";
    }
    cout<<endl;
 
 
 
 
 
// cout<<ans;
    // cout<<a.size();
    // for (auto i: a){cout<<i<<" ";}
}
signed main(){
    Code by Hayan
    int ans=1;
    //cout<<setprecision(1000);
    // cin>>ans;
    while(ans--){
        // cout << "Case #" << ans << ": \n";
        solve();ln;}}

Compilation message

carnival.cpp: In function 'bool q(long long int)':
carnival.cpp:64:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   64 |     for (auto i: a)
      |     ^~~
carnival.cpp:65:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   65 |         cout<<i<<" ";cout<<x<<" ";cout<<endl;
      |                      ^~~~
carnival.cpp:67:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   67 |     return a.size()!=e;
      |            ~~~~~~~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 3 ms 452 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 2 ms 344 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 4 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 3 ms 344 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 4 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 3 ms 344 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 3 ms 456 KB Output is correct
6 Correct 2 ms 456 KB Output is correct
7 Correct 3 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 4 ms 452 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 3 ms 456 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct