oj.uz

Submission #97006

# Submission time Handle Problem Language Result Execution time Memory
97006 2019-02-13T09:00:16 Z Kastanda Carnival (CEOI14_carnival) C++11
0 / 100
 17 ms 384 KB 
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 155;
int n, ts, C[N], _C[N];
vector < int > res;
/*void Prnt(vector < int > A)
{
    for (int id : A)
        printf("%d ", id);
    printf("\n");
}*/
inline int Query(vector < int > vec)
{
    sort(vec.begin(), vec.end());
    printf("%d", (int)vec.size());
    for (int id : vec)
        printf(" %d", id + 1);
    printf("\n"); fflush(stdout);
    int k; scanf("%d", &k);
    return (k);
}
inline int Query(vector < int > vec1, vector < int > vec2)
{
    for (int id : vec2)
        vec1.pb(id);
    vec2.clear();
    return Query(vec1);
}
vector < int > GetCmp(vector < int > &A)
{
    set < int > S;
    vector < int > R;
    for (int i = 0; i < A.size(); i++)
        if (!S.count(C[A[i]]))
            R.pb(A[i]), S.insert(C[A[i]]);
    return (R);
}
void GoForIt(vector < int > A, vector < int > B)
{
    if (!B.size())
        return ;
    if (B.size() == 1)
    {
        res.pb(B[0]);
        return ;
    }
    vector < int > B1, B2;
    for (int i = 0; i < (int)B.size(); i++)
    {
        if (i < ((int)B.size() >> 1))
            B1.pb(B[i]);
        else
            B2.pb(B[i]);
    }
    int K1 = Query(A, B1);
    int K2 = Query(A, B2);
    if (A.size() + B1.size() > K1)
        GoForIt(A, B1);
    if (A.size() + B2.size() > K2)
        GoForIt(A, B2);
    return ;
}
void Solve(vector < int > A)
{
    for (int id : A)
        C[id] = ts;
    ts ++;
    if ((int)A.size() <= 3)
    {
        if (A.size() >= 2 && Query(vector < int > {A[0], A[1]}) > 1)
            C[A[1]] = ts ++;
        if (A.size() >= 3 && Query(vector < int > {A[0], A[2]}) > 1)
        {
            C[A[2]] = ts - 1;
            if (C[A[0]] != C[A[1]] && (Query(vector < int > {A[1], A[2]}) > 1))
                C[A[2]] = ts ++;
        }
        return ;
    }
    int K = Query(A);
    if (K <= 1)
        return ;
    // Perhaps shuffle it a little bit ...
    vector < int > L, R;
    for (int i = 0; i < (int)A.size(); i++)
    {
        if (i < (((int)A.size() + 1) >> 1))
            L.pb(A[i]);
        else
            R.pb(A[i]);
    }
    Solve(L); Solve(R);
    vector < int > Cl = GetCmp(L);
    vector < int > Cr = GetCmp(R);
    int Kl = Cl.size(), Kr = Cr.size();
    if (Kl + Kr == K)
        return ;
    GoForIt(Cr, Cl);
    vector < int > le = res;
    res.clear();
    for (int id : le)
    {
        GoForIt(vector < int > {id}, Cr);
        int ri = res[0]; res.clear();
        for (int i = 1; i <= n; i++)
            if (i != ri && C[i] == C[ri])
                C[i] = C[id];
        C[ri] = C[id];
    }
    return ;
}
int main()
{
    scanf("%d", &n);
    vector < int > P(n, 0);
    iota(P.begin(), P.end(), 0);
    Solve(P);
    set < int > S;
    for (int i = 0; i < n; i++)
        S.insert(C[i]);
    ts = 0;
    for (int c : S)
    {
        ts ++;
        for (int i = 0; i < n; i++)
            if (C[i] == c)
                _C[i] = ts;
    }
    printf("0");
    for (int i = 0; i < n; i++)
        printf(" %d", _C[i]);
    printf("\n"); fflush(stdout);
    return 0;
}

Compilation message

carnival.cpp: In function 'std::vector<int> GetCmp(std::vector<int>&)':
carnival.cpp:34:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < A.size(); i++)
                     ~~^~~~~~~~~~
carnival.cpp: In function 'void GoForIt(std::vector<int>, std::vector<int>)':
carnival.cpp:58:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (A.size() + B1.size() > K1)
         ~~~~~~~~~~~~~~~~~~~~~^~~~
carnival.cpp:60:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (A.size() + B2.size() > K2)
         ~~~~~~~~~~~~~~~~~~~~~^~~~
carnival.cpp: In function 'int Query(std::vector<int>)':
carnival.cpp:20:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int k; scanf("%d", &k);
            ~~~~~^~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 256 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 256 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 7 ms 320 KB Output is correct
3 Correct 16 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Incorrect 8 ms 384 KB Incorrect
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 384 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 384 KB Incorrect
2 Halted 0 ms 0 KB -