Submission #858411

#	Time	Username	Problem	Language	Result	Execution time	Memory
858411		_uros9	Carnival (CEOI14_carnival)	C++17	100 / 100	17 ms	1460 KiB

carnival

#include <bits/stdc++.h>

using namespace std;

int ask(vector<int>&v){
    if(v.size()==1) return 1;
    cout << v.size() << " ";
    for(auto&x:v)
        cout << x << " ";
    cout << endl << flush;
    int odg;cin >> odg;
    return odg;
}

void deo1(int n,vector<vector<int>>&delovi,int tr_ind){
    if(tr_ind==n+1) return;
    int l=tr_ind,d=n,rez;
    while(l<=d){
        int s=(l+d)/2;
        vector<int> pitaj(0);
        for(int i=tr_ind; i<=s; i++)
            pitaj.push_back(i);
        if(ask(pitaj)==pitaj.size()){
            rez=s;
            l=s+1;
        }
        else
            d=s-1;
    }
    vector<int> p(0);
    for(int i=tr_ind; i<=rez; i++)
        p.push_back(i);
    delovi.push_back(p);
    deo1(n,delovi,rez+1);
}
vector<int> par,rnk;
int ulp(int node){
    if(par[node]==node) return node;
    return par[node]=ulp(par[node]);
}
void spajaj(int a,int b){
    a=ulp(a);b=ulp(b);
    if(a==b) return;
    if(rnk[b]>rnk[a])
        swap(a,b);
    par[b]=a;
    if(rnk[b]==rnk[a])
        rnk[a]++;
}

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> delovi(0);
    deo1(n,delovi,1);
    int tr_deo=0;
    rnk.resize(n+1,0);
    par.resize(n+1);
    for(int i=1; i<=n; i++)
        par[i]=i;
    vector<bool> checked(n+1,0);
    vector<int> pocetak_dela(delovi.size()+1);
    pocetak_dela[0]=1;
    for(int i=1; i<delovi.size(); i++)
        pocetak_dela[i]=pocetak_dela[i-1]+delovi[i-1].size();
    pocetak_dela[delovi.size()]=pocetak_dela[delovi.size()-1]+delovi[delovi.size()-1].size();
    //cerr << "Zavrsio prvi deo" << endl;
    while(tr_deo!=delovi.size()-1){
        for(auto tr_element:delovi[tr_deo]){
            if(checked[tr_element]) continue;
            for(int i=tr_deo+1; i<delovi.size(); i++){
                vector<int> pp(0);
                pp.push_back(tr_element);
                int l=pocetak_dela[i],d=pocetak_dela[i+1]-1;
                for(int j=l; j<=d; j++)
                    pp.push_back(j);
                if(ask(pp)==pp.size())
                    continue;
                int rez=2e5;
                while(l<=d){
                    int s=(l+d)/2;
                    vector<int> p(0);
                    p.push_back(tr_element);
                    for(int j=pocetak_dela[i]; j<=s; j++)
                        p.push_back(j);
                    int odg=ask(p);
                    if(odg>=p.size())
                        l=s+1;
                    else{
                        rez=min(rez,s);
                        d=s-1;
                    }
                }
                spajaj(tr_element,rez);
                checked[rez]=true;
            }
        }
        tr_deo++;
    }
    vector<int> rez(n),mapa(n+2,0);
    int tr_boja=1;
    for(int i=1; i<=n; i++){
        if(mapa[ulp(i)]==0){
            mapa[ulp(i)]=tr_boja;
            tr_boja++;
        }
    }
    for(int i=1; i<=n; i++)
        rez[i-1]=mapa[ulp(i)];
    cout << 0 << " ";
    for(auto x:rez)
        cout << x << " ";
    cout << flush;


    return 0;
}

Compilation message (stderr)

carnival.cpp: In function 'void deo1(int, std::vector<std::vector<int> >&, int)':
carnival.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if(ask(pitaj)==pitaj.size()){
      |            ~~~~~~~~~~^~~~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=1; i<delovi.size(); i++)
      |                  ~^~~~~~~~~~~~~~
carnival.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     while(tr_deo!=delovi.size()-1){
      |           ~~~~~~^~~~~~~~~~~~~~~~~
carnival.cpp:72:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for(int i=tr_deo+1; i<delovi.size(); i++){
      |                                 ~^~~~~~~~~~~~~~
carnival.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |                 if(ask(pp)==pp.size())
      |                    ~~~~~~~^~~~~~~~~~~
carnival.cpp:88:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |                     if(odg>=p.size())
      |                        ~~~^~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20