oj.uz

Submission #313612

# Submission time Handle Problem Language Result Execution time Memory
313612 2020-10-16T11:51:17 Z Ahmad_Hasan Carnival (CEOI14_carnival) C++17
100 / 100
 9 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;
/**
struct st1d{
    int sz=2;
    vector<int>vls;
    void init(int n){
        while(sz<n) sz*=2;
        vls=vector<int>(2*sz,0);
    }

    void update(int i,int vl,int x,int lx,int rx){

        ///cout<<lx<<' '<<rx<<'\n';
        if(rx==lx){
            vls[x]+=vl;
            return;
        }
        int mid=(lx+rx)/2;
        if(i<=mid)
        update(i,vl,2*x,lx,mid);
        else
        update(i,vl,2*x+1,mid+1,rx);
        vls[x]=vls[2*x]+vls[2*x+1];
    }

    void update(int i,int vl){
        update(i,vl,1,0,sz-1);
    }

    int get(int l,int r,int x,int lx,int rx){
        if(rx<l||lx>r) return 0;
        if(lx>=l&&rx<=r){
            return vls[x];
        }
        int mid=(lx+rx)/2;
        return get(l,r,2*x,lx,mid)+get(l,r,2*x+1,mid+1,rx);
    }

    int get(int l,int r){
        return get(l,r,1,0,sz-1);
    }
    void print(){
        for(int i=1;i<=2*sz;i*=2){
            for(int j=i/2;j<i;j++)
                cout<<vls[j]<<' ';
            cout<<'\n';
        }
    }

};
struct st2d{
    int sz=2;
    vector<st1d>vls;
    void init(int n,int m){
        while(sz<n) sz*=2;
        st1d tmp;
        tmp.init(m);
        vls=vector<st1d>(2*sz,tmp);
    }

    void update(int ix,int iy,int vl,int x,int lx,int rx){

        ///cout<<lx<<' '<<rx<<'\n';
        if(rx==lx){
            vls[x].update(iy,vl);
            return;
        }
        int mid=(lx+rx)/2;
        if(ix<=mid)
        update(ix,iy,vl,2*x,lx,mid);
        else
        update(ix,iy,vl,2*x+1,mid+1,rx);
        vls[x].update(iy,vl);
    }

    void update(int ix,int iy,int vl){
        update(ix,iy,vl,1,0,sz-1);
    }

    int get(int xl,int xr,int yl,int yr,int x,int lx,int rx){
        if(rx<xl||lx>xr) return 0;
        if(lx>=xl&&rx<=xr){
            return vls[x].get(yl,yr);
        }
        int mid=(lx+rx)/2;
        return get(xl,xr,yl,yr,2*x,lx,mid)+get(xl,xr,yl,yr,2*x+1,mid+1,rx);
    }

    int get(int xl,int xr,int yl,int yr){
        return get(xl,xr,yl,yr,1,0,sz-1);
    }
    void print(){
        for(int i=1;i<=2*sz;i*=2){
            for(int j=i/2;j<i;j++)
                cout<<vls[j].get(0,sz-1)<<' ';
            cout<<'\n';
        }
    }

};
**/



int main()
{
     int n;
     cin>>n;
     vector<int>qury,id(n+5);
     int cnt=1;
    int dists;
     for(int i=1;i<=n;i++){
        qury.push_back(i);
        cout<<qury.size()<<' ';
        for(int j=0;j<qury.size();j++)
            cout<<qury[j]<<' ';
        cout<<'\n';
        fflush(stdout);
        cin>>dists;
        if(dists==qury.size()){
            id[i]=cnt;
            cnt++;
        }else{
            int l=0,r=qury.size()-2;
            dists=0;
            while(dists!=1){
                int mid=(r-l)/2+l;
                vector<int>nqury;
                for(int j=l;j<=mid;j++)
                    nqury.push_back(qury[j]);
                nqury.push_back(i);
                cout<<nqury.size()<<' ';
                for(int j=0;j<nqury.size();j++)
                    cout<<nqury[j]<<' ';
                cout<<'\n';
                fflush(stdout);
                cin>>dists;
                if(dists<nqury.size()){
                    r=mid;
                    if(dists==1)
                        id[i]=id[nqury[0]];
                }else{
                    l=mid+1;
                }
            }
            qury.erase(qury.begin()+qury.size()-1);
        }
     }
     cout<<0<<' ';
    for(int j=1;j<=n;j++)
        cout<<id[j]<<' ';
    cout<<'\n';
    fflush(stdout);
    return 0;
}

/***
1 4
100 100 100 100

*/

Compilation message

carnival.cpp: In function 'int main()':
carnival.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for(int j=0;j<qury.size();j++)
      |                     ~^~~~~~~~~~~~
carnival.cpp:122:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         if(dists==qury.size()){
      |            ~~~~~^~~~~~~~~~~~~
carnival.cpp:135:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |                 for(int j=0;j<nqury.size();j++)
      |                             ~^~~~~~~~~~~~~
carnival.cpp:140:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |                 if(dists<nqury.size()){
      |                    ~~~~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 256 KB Output is correct
2 Correct 7 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 9 ms 256 KB Output is correct
6 Correct 8 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

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