oj.uz

Submission #553193

# Submission time Handle Problem Language Result Execution time Memory
553193 2022-04-25T03:53:22 Z fcmalkcin Carnival (CEOI14_carnival) C++17
100 / 100
 12 ms 464 KB 
//#include "gap.h"

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
//#define endl "\n"
#define pb push_back
#define F(i,a,b) for(ll i=a;i<=b;i++)

const ll maxn=3e5+100;
const ll base=3e18;
const ll mod= 1e9+7 ;

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

ll par[maxn];
ll find_par(ll u)
{
    if (u==par[u]) return u;
    return par[u]=find_par(par[u]);
}
void dsu(ll x,ll y)
{
    x=find_par(x);
    y=find_par(y);
    if (x==y) return ;
    par[x]=y;
}
ll ask(vector<ll> vt)
{
    cout <<vt.size()<<" ";
    for (auto to:vt) cout <<to<<" ";
    cout <<endl;
    ll x;
    cin>> x;
    return x;
}
vector<ll> dosth(ll l,ll r)
{
    vector<ll> vt;
    if (l==r)
    {
        par[l]=l;
        vt.pb(l);
        return vt;
    }
    ll mid=(l+r)/2;
    auto p=dosth(l,mid);
    auto p1=dosth(mid+1,r);
    for (auto to:p)
    {
        ll sl=p1.size();
        vector<ll> nw=p1;
        nw.pb(to);
        if (ask(nw)==sl)
        {
            ll l=0,h=p1.size()-1;
            while (l<=h)
            {
                ll mid=(l+h)/2;
                vector<ll> nw;
                nw.pb(to);
                for (int i=0;i<=mid;i++) nw.pb(p1[i]);
                if (ask(nw)==(mid+1)) h=mid-1;
                else l=mid+1;
            }
            dsu(to,p1[l]);
        }
    }
    vector<ll> res;
    for (auto to:p)
    {
        if (to==find_par(to)) res.pb(to);
    }
    for (auto to:p1)
    {
        if (to==find_par(to)) res.pb(to);
    }
    return res;
}
ll col[maxn];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    ll n;
    cin>> n;
    dosth(1,n);
    ll cnt=0;
    for (int i=1;i<=n;i++)
    {
        if (i==find_par(i)) cnt++,col[i]=cnt;
    }
    cout <<0<<" ";
    for (int i=1;i<=n;i++) cout <<col[find_par(i)]<<" ";
    cout <<endl;
}

Compilation message

carnival.cpp: In function 'int main()':
carnival.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
carnival.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 464 KB Output is correct
2 Correct 10 ms 336 KB Output is correct
3 Correct 8 ms 336 KB Output is correct
4 Correct 8 ms 344 KB Output is correct
5 Correct 6 ms 208 KB Output is correct
6 Correct 4 ms 208 KB Output is correct
7 Correct 10 ms 340 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 10 ms 340 KB Output is correct
3 Correct 7 ms 340 KB Output is correct
4 Correct 7 ms 348 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 5 ms 336 KB Output is correct
7 Correct 7 ms 336 KB Output is correct

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

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