oj.uz

Submission #619980

# Submission time Handle Problem Language Result Execution time Memory
619980 2022-08-02T18:07:12 Z Omar_Fakhry Carnival (CEOI14_carnival) C++17
100 / 100
 20 ms 336 KB 
//بسم الله الرحمن الرحيم
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pi 3.14159265358979323846
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define For(start,end,step) for(ll i=start;i<=end;i+=step)
#define For2(start,end,step) for(ll j=start;j<=end;j+=step)
#define mult(x,y) x*(y-1)
#define ALL(x) x.begin(), x.end()
using namespace std;
using namespace __gnu_pbds;
const ll mod=1e9+7;
bool prime(ll n)
{
for(int i=2;i*i<=n;i++)if(n%i==0)return 0;
return 1;
}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll po(ll x,ll y)
{
    if(y==0) return 1;
    ll ret=po(x,y/2);
    ret=(ret*ret);
    if(y&1)
        return (x*ret);
    return ret;
}
ll sigma(ll s,ll e,ll num_elements)
{
    ll res1=s+e;
    ll res=(((s+e)/2)*(num_elements));
    if(res1%2)res+=num_elements/2;
    return res;
}
ll mod_inverse(ll x)
{
    return po(x,mod-2);
}
string bin(ll x)
{
    string str="";
    while(x)
    {
        if(x%2)
        {
            str+='1';
        }
        else
        {
            str+='0';
        }
        x/=2;
    }
    return str;
}
ll GP(ll base,ll power,ll step)
{
    return (po(base,power+step)+mod-1)%mod*mod_inverse(po(base,step)-1)%mod;
}
ll fact(ll x)
{
    if(x<2)return 1;
    return x*fact(x-1)%mod;
}
ll ncr(ll x,ll y)
{
    return fact(x)*mod_inverse(fact(y)*fact(x-y)%mod)%mod;
}
bool valid(ll x,ll y,ll n,ll m)
{
    return(x>=0&&y>=0&&x<n&&y<m);
}
int dx[8]= {0,0,1,-1,-1,1,1,-1};
int dy[8]= {-1,1,0,0,-1,1,-1,1};

const int N=55;

int n;
int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt","w",stdout);
    cin>>n;
    vector<int>vec;
    int cnt=1;
    vector<int>ans(n+1);
    ans[1]=cnt++;
    vec.push_back(1);
    for(int i=2;i<=n;i++)
    {
        int s=0,e=vec.size()-1;
        int temp3=-1;
        while(s<=e)
        {
            int mid=(s+e)/2;
            int temp=vec.size()-mid;
            int length=i-vec[mid]+1;
            cout<<length<<' ';
            for(int j=vec[mid];j<=i;j++)
            {
                cout<<j<<' ';
            }
            cout<<'\n';
            int temp2;cin>>temp2;
            if(temp2==temp)
            {
                temp3=mid;
                s=mid+1;
            }
            else
            {
                e=mid-1;
            }
        }
        if(temp3==-1)
        {
            ans[i]=cnt++;
            vec.push_back(i);
        }
        else
        {
            //cout<<temp3<<'\n';
            ans[i]=ans[vec[temp3]];
            vector<int>vec2;
            for(int j=vec.size()-1;j>temp3;j--)
            {
                vec2.push_back(vec.back());
                vec.pop_back();
            }
            vec.pop_back();
            for(int j=vec2.size()-1;j>-1;j--)vec.push_back(vec2[j]);
            vec.push_back(i);
        }
        //for(int j=0;j<vec.size();j++)cout<<vec[j]<<' ';
        //cout<<'\n';
    }
    cout<<"0 ";
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
    cout<<'\n';
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 208 KB Output is correct
2 Correct 4 ms 208 KB Output is correct
3 Correct 12 ms 208 KB Output is correct
4 Correct 20 ms 280 KB Output is correct
5 Correct 8 ms 208 KB Output is correct
6 Correct 11 ms 208 KB Output is correct
7 Correct 13 ms 208 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 208 KB Output is correct
2 Correct 6 ms 208 KB Output is correct
3 Correct 11 ms 208 KB Output is correct
4 Correct 9 ms 296 KB Output is correct
5 Correct 11 ms 208 KB Output is correct
6 Correct 17 ms 208 KB Output is correct
7 Correct 10 ms 208 KB Output is correct