Submission #125566

#	Time	Username	Problem	Language	Result	Execution time	Memory
125566		eriksuenderhauf	Carnival (CEOI14_carnival)	C++11	100 / 100	29 ms	436 KiB

carnival

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e3 + 5;
const double eps = 1e-9;
int ans[MAXN], par[MAXN], vis[MAXN];
int BLOCK = 13, n;
set<pii> dp;

int qry(int x) {
    if (x == par[x])
        return x;
    return par[x] = qry(par[x]);
}

void _join(int u, int v) {
    u = qry(u), v = qry(v);
    par[v] = u;
}

void _join2(int u, int v) {
    dp.insert({u, v});
}

int ask(vi a) {
    printf("%d ", (int)a.size());
    for (int i = 0; i < a.size(); i++) {
        if (i == a.size() - 1)
            printf("%d\n", a[i]);
        else
            printf("%d ", a[i]);
    }
    fflush(stdout);
    int tmp; ni(tmp);
    return tmp;
}

int main()
{
    for (int i = 0; i < MAXN; i++)
        par[i] = i;
    ni(n);
    while (1) {
        vi cur;
        for (int i = 1; i <= n; i++) {
            if (cur.size() + 1 < BLOCK) {
                if (!vis[i]) {
                    cur.pb(i);
                    vis[i] = 1;
                }
            } else {
                cur.pb(i);
                if (ask(cur) > BLOCK)
                    cur.pop_back();
                else
                    vis[i] = 1;
            }
        }
        if (cur.empty())
            break;
        sort(cur.begin(), cur.end());
        for (int i = 0; i < cur.size(); i++) {
            for (int j = i + 1; j < cur.size(); j++) {
                int x = qry(cur[i]), y = qry(cur[j]);
                if (x > y) swap(x, y);
                if (x == y || qry(cur[i]) != cur[i] || dp.find({x, y}) != dp.end())
                    continue;
                if (ask({cur[i], cur[j]}) == 1)
                    _join(cur[i], cur[j]);
                else
                    _join2(cur[i], cur[j]);
            }
        }
    }
    int cnt = 1;
    for (int i = 1; i <= n; i++)
        if (qry(i) == i)
            ans[i] = cnt++;
    printf("0 ");
    for (int i = 1; i <= n; i++)
        if (i != n)
            printf("%d ", ans[qry(i)]);
        else
            printf("%d\n", ans[qry(i)]);
    fflush(stdout);
    return 0;
}

Compilation message (stderr)

carnival.cpp: In function 'int ask(std::vector<int>)':
carnival.cpp:51:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); i++) {
                     ~~^~~~~~~~~~
carnival.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == a.size() - 1)
             ~~^~~~~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:70:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (cur.size() + 1 < BLOCK) {
                 ~~~~~~~~~~~~~~~^~~~~~~
carnival.cpp:86:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < cur.size(); i++) {
                         ~~^~~~~~~~~~~~
carnival.cpp:87:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = i + 1; j < cur.size(); j++) {
                                 ~~^~~~~~~~~~~~
carnival.cpp: In function 'int ask(std::vector<int>)':
carnival.cpp:7:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
carnival.cpp:58:14: note: in expansion of macro 'ni'
     int tmp; ni(tmp);
              ^~
carnival.cpp: In function 'int main()':
carnival.cpp:7:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
carnival.cpp:66:5: note: in expansion of macro 'ni'
     ni(n);
     ^~

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