oj.uz

Submission #927932

# Submission time Handle Problem Language Result Execution time Memory
927932 2024-02-15T14:10:41 Z emad234 Carnival (CEOI14_carnival) C++17
100 / 100
 12 ms 704 KB 
// #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.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 7 ms 452 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 9 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 11 ms 448 KB Output is correct
4 Correct 9 ms 452 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 448 KB Output is correct
7 Correct 8 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 344 KB Output is correct
3 Correct 6 ms 448 KB Output is correct
4 Correct 8 ms 452 KB Output is correct
5 Correct 7 ms 452 KB Output is correct
6 Correct 7 ms 448 KB Output is correct
7 Correct 12 ms 704 KB Output is correct