Submission #1161873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161873		simona1230	사육제 (CEOI14_carnival)	C++17	100 / 100	8 ms	412 KiB

carnival

#include <bits/stdc++.h>
using namespace std;

int n;
int a[151],c[151];

int query(int l,int r,int id)
{
    int sz=r-l+1;
    if(id!=-1)sz++;
    cout<<sz<<" ";
    for(int i=l;i<=r;i++)
        cout<<i<<" ";
    if(id!=-1)cout<<id<<endl;
    else cout<<endl;
    int x;
    cin>>x;
    return x;
}
int y[151];

void rec(int l,int r)
{
    if(l==r)
    {
        a[l]=1;
        return;
    }

    if(l>r)return;

    int m=(l+r)/2;
    rec(l,m);
    rec(m+1,r);

    int num=1,diff;
    y[l]=1;
    for(int i=l+1;i<=m;i++)
    {
        y[i]=y[i-1];
        if(num<a[i])y[i]++;
        num=max(num,a[i]);
    }
    diff=num;
    for(int i=m+1;i<=r;i++)
        c[a[i]]=0;

    for(int i=m+1;i<=r;i++)
    {
        if(c[a[i]])
        {
            a[i]=c[a[i]];
            continue;
        }
        int lf=l,rt=m;
        int idx=-1;
        while(lf<=rt)
        {
            int md=(lf+rt)/2;
            if(query(l,md,i)==y[md])
            {
                idx=md;
                rt=md-1;
            }
            else lf=md+1;
        }

        if(idx==-1)
        {
            diff++;
            c[a[i]]=diff;
            a[i]=diff;
        }
        else
        {
            c[a[i]]=a[idx];
            a[i]=a[idx];
        }
    }
}
int main()
{
    cin>>n;
    rec(1,n);
    cout<<0<<" ";
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}

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