oj.uz

답안 #125565

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125565 2019-07-06T00:27:03 Z eriksuenderhauf 사육제 (CEOI14_carnival) C++11
100 / 100
 27 ms 424 KB 
//#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 abc=0;

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);
    //abc++;
    return tmp;
}

/*// solve from l (inclusive) to r (exclusive)
void solve(int l, int r) {
    for (int i = l; i < min(n+1, r); i++) {
        if (qry(i) != i)
            continue;
        for (int j = i + 1; j < min(n+1, r); j++) {
            int tmp = ask(i, j);
            if (tmp == 1) {
                _join(i, j);
            } else {
                _join2(i, j);
            }
        }
    }
}

void join(int a, int b, int c, int d) {
    for (int i = a; i < min(n+1,b); i++) {
        for (int j = c; j < min(n+1, d); j++) {
            int x = qry(i), y = qry(j);
            if (x > y) swap(x, y);
            if (x == y || dp.find({x, y}) != dp.end())
                continue;
            int tmp = ask(i, j);
            if (tmp == 1) {
                _join(i, j);
            } else {
                _join2(i, j);
            }
        }
    }
}*/

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);
    //pri(abc);
    return 0;
}

Compilation message

carnival.cpp: In function 'int ask(std::vector<int>)':
carnival.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); i++) {
                     ~~^~~~~~~~~~
carnival.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == a.size() - 1)
             ~~^~~~~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:106:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (cur.size() + 1 < BLOCK) {
                 ~~~~~~~~~~~~~~~^~~~~~~
carnival.cpp:122:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < cur.size(); i++) {
                         ~~^~~~~~~~~~~~
carnival.cpp:123: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:60: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:102:5: note: in expansion of macro 'ni'
     ni(n);
     ^~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 248 KB Output is correct
2 Correct 15 ms 376 KB Output is correct
3 Correct 19 ms 248 KB Output is correct
4 Correct 10 ms 328 KB Output is correct
5 Correct 6 ms 248 KB Output is correct
6 Correct 5 ms 248 KB Output is correct
7 Correct 16 ms 372 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 248 KB Output is correct
2 Correct 19 ms 376 KB Output is correct
3 Correct 14 ms 424 KB Output is correct
4 Correct 10 ms 328 KB Output is correct
5 Correct 5 ms 408 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 12 ms 376 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 12 ms 252 KB Output is correct
3 Correct 12 ms 424 KB Output is correct
4 Correct 11 ms 328 KB Output is correct
5 Correct 6 ms 324 KB Output is correct
6 Correct 8 ms 324 KB Output is correct
7 Correct 20 ms 252 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 248 KB Output is correct
2 Correct 6 ms 328 KB Output is correct
3 Correct 11 ms 324 KB Output is correct
4 Correct 12 ms 328 KB Output is correct
5 Correct 11 ms 376 KB Output is correct
6 Correct 18 ms 248 KB Output is correct
7 Correct 16 ms 360 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 248 KB Output is correct
2 Correct 10 ms 416 KB Output is correct
3 Correct 11 ms 324 KB Output is correct
4 Correct 19 ms 376 KB Output is correct
5 Correct 18 ms 376 KB Output is correct
6 Correct 27 ms 328 KB Output is correct
7 Correct 21 ms 248 KB Output is correct