Submission #164889

#	Time	Username	Problem	Language	Result	Execution time	Memory
164889		arnold518	Carnival (CEOI14_carnival)	C++14	100 / 100	32 ms	568 KiB

carnival

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 150;

int N, ans[MAXN+10], cnt;
map<vector<int>, int> M;

int ask(vector<int> V)
{
    if(M.find(V)!=M.end()) return M[V];
    printf("%d ", V.size());
    for(auto it : V) printf("%d ", it); printf("\n");
    fflush(stdout);

    int t;
    scanf("%d", &t);
    M[V]=t;
    return t;
}

bool query(int l, int r, int k)
{
    int i;
    vector<int> V1, V2;
    for(i=l; i<=r; i++) V1.push_back(i), V2.push_back(i);
    V2.push_back(k);
    return ask(V1)==ask(V2);
}

int main()
{
    int i, j;

    scanf("%d", &N);
    ans[1]=1; cnt=2;
    for(i=2; i<=N; i++)
    {
        if(!query(1, i-1, i)) ans[i]=cnt++;
        else
        {
            int lo=1, hi=i-1;
            while(lo<hi)
            {
                int mid=lo+hi>>1;
                if(query(lo, mid, i)) hi=mid;
                else lo=mid+1;
            }
            ans[i]=ans[lo];
        }
    }
    printf("0 ");
    for(i=1; i<=N; i++) printf("%d ", ans[i]);
}

Compilation message (stderr)

carnival.cpp: In function 'int ask(std::vector<int>)':
carnival.cpp:16:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d ", V.size());
                   ~~~~~~~~^
carnival.cpp:17:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(auto it : V) printf("%d ", it); printf("\n");
     ^~~
carnival.cpp:17:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(auto it : V) printf("%d ", it); printf("\n");
                                         ^~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:49:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                 int mid=lo+hi>>1;
                         ~~^~~
carnival.cpp:37:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
carnival.cpp: In function 'int ask(std::vector<int>)':
carnival.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &t);
     ~~~~~^~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~

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