oj.uz

Submission #996008

# Submission time Handle Problem Language Result Execution time Memory
996008 2024-06-10T07:11:58 Z vjudge1 Carnival (CEOI14_carnival) C++14
100 / 100
 7 ms 344 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define ii pair<int,int>
#define ill pair<ll,ll>
#define el cout<<'\n'
const ll mod=1e9+7;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int nmax=1e5;

void add ( int&a , int b ) { if ((a+=b) > mod ) a -= mod ; }
void sub ( int&a , int b ) { if ((a-=b) < 0 ) a += mod ; }

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

using namespace std;
vector<int>a;
int cnt=0;
int ans[nmax+5];
vector<int>dele;
bool check(int l,int r,int st)
{
    int tmp1=1,tmp2;
    if(r>l){
    cout<<(r-l+1)<<" ";
    for(int i=l;i<=r;i++)
        cout<<a[i]<<" ";
    fflush(stdout);
    cin>>tmp1;
    }
    cout<<(r-l+2)<<" "<<st<<" ";
    for(int i=l;i<=r;i++)
        cout<<a[i]<<" ";
    fflush(stdout);
    cin>>tmp2;
  //  cout<<l<<" "<<r
    return(tmp1==tmp2);
}
void segment(int l,int r,int st)
{

    //int mid=(l+r)/2;
    //if(l>r)
      //  return;
    if(l==r)
    {
        dele.pb(a[l]);
        ans[a[l]]=cnt;
        return ;
    }
    int mid=(l+r)/2;
    if(check(l,mid,st)) {segment(l,mid,st);
    if(check(mid+1,r,st)) segment(mid+1,r,st);
    }
    else
    {
        segment(mid+1,r,st);
    }
}
int main()
{
   ios::sync_with_stdio(0);
  // cin.tie(0);cout.tie(0);
   int n;
   cin>>n;
   for(int i=1;i<=n;i++)
    a.pb(i);
   while(!a.empty())
   {
        cnt++;
        ans[a[0]]=cnt;
        if(a.size()==1)
        {

            break;
        }
        int tmp=a[0];
        dele.clear();
        if(check(1,a.size()-1,tmp))
        segment(1,a.size()-1,tmp);

        sort(dele.begin(),dele.end(),greater<int>());
        for(auto i:dele){
            auto it = find(a.begin(), a.end(),i);
          //  cout<<i<<" ";
            a.erase(it);
        }
      //  cout<<a.size()<<"wtf";el;
        //if()
        if(!a.empty()){
        auto it=a.begin();
        a.erase(it);
        }
      //  cout<<a.size()<<" "<<a[0]<<"jj";el;
   }
   cout<<"0 ";
   for(int i=1;i<=n;i++)
    cout<<ans[i]<<" ";
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

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