Submission #125566

#TimeUsernameProblemLanguageResultExecution timeMemory
125566eriksuenderhaufCarnival (CEOI14_carnival)C++11
100 / 100
29 ms436 KiB
//#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);
     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...