Submission #927932

#	Time	Username	Problem	Language	Result	Execution time	Memory
927932		emad234	Carnival (CEOI14_carnival)	C++17	100 / 100	12 ms	704 KiB

carnival

// #pragma GCC optimize("O3")
// #pragma GCC tagret("avx2")
#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pii pair<int,int>
const int mod = 1e9 + 7;
const int mxN = 2e5 + 5;
using namespace std;
int dsu[mxN];
int find(int x){return (dsu[x] == x ? x : dsu[x] = find(dsu[x]));}
void merge(int a,int b){
  int fa = find(a),fb = find(b);
  dsu[fb] = fa;
}
bool vis[mxN];
signed main(){
  // ios_base::sync_with_stdio(0);
  // cin.tie(0);
  // cout.tie(0);
  int n;
  cin >>n;
  for(int i = 1;i <= n;i++){
    dsu[i] = i;
  }
  int bg = 1;
  vector<int>v;
  v.push_back(1);
  for(int i = 2;i <= n;i++){
    cout.flush()<<i - bg + 1<<' ';
    for(int j = bg;j <= i;j++){
      cout.flush()<<j<<' ';
    }
    cout<<endl;
    int sz;cin>>sz;
    if(sz == 1) merge(bg,i);
    else{
      bg = i;
      int l = 0,r = v.size() - 1;
      int md;
      bool done =0;
      while(l <= r){
        md = (l + r) / 2;
        cout.flush()<<md - l + 2<<' ';
        for(int j = l;j <= md;j++){
          cout.flush()<<v[j]<<' ';
        }
        cout.flush()<<i<<endl;
        cin >>sz;
        if(sz == 1 && r == l){
          done = 1;
          break;
        }else if(md == l && sz == 2){

        }
        if(sz < md - l + 2) r = md;
        else l = md + 1;
      }
      if(done) merge(v[md],i);
      else v.push_back(i);
    }
  }
  vector<int>id;
  for(int i = 1;i <= n;i++){
    if(!vis[find(i)]) id.push_back(find(i));
    vis[find(i)] = 1;
  }
  cout.flush()<<0<<' ';
  for(int i = 1;i <= n;i++) cout.flush()<<lower_bound(id.begin(),id.end(),find(i)) - id.begin() + 1<<' ';
  cout.flush()<<endl;
  return 0;
}

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