Submission #725812

#	Time	Username	Problem	Language	Result	Execution time	Memory
725812		becaido	Scales (IOI15_scales)	C++17	100 / 100	7 ms	368 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

scales

#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,popcnt,sse4,abm") #include <bits/stdc++.h> #include "scales.h" using namespace std; #define ll long long #define Waimai ios::sync_with_stdio(false), cin.tie(0) #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++) #define pb emplace_back #define F first #define S second const int MAX = 720; array<int, 6> P[MAX]; int pos[MAX][7]; struct Tree { int ty, a, b, c, d; Tree *nxt[3]; Tree() {} Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {} tuple<int, int, int, int, int> id() { return {ty, a, b, c, d}; } }; Tree *root; bool build(Tree *&t, vector<int> cur, int lim) { if (cur.size() <= 1) return 1; t = new Tree(); FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) { *t = Tree(ty, i, j, k); vector<int> vi, vj, vk; bool f = 1; for (int id : cur) { int cp; if (ty == 1) cp = min({pos[id][i], pos[id][j], pos[id][k]}); if (ty == 2) cp = max({pos[id][i], pos[id][j], pos[id][k]}); if (ty == 3) cp = pos[id][i] + pos[id][j] + pos[id][k] - min({pos[id][i], pos[id][j], pos[id][k]}) - max({pos[id][i], pos[id][j], pos[id][k]}); (pos[id][i] == cp ? vi : pos[id][j] == cp ? vj : vk).pb(id); if (max({vi.size(), vj.size(), vk.size()}) > lim) { f = 0; break; } } if (f) f &= build(t->nxt[0], vi, lim / 3); if (f) f &= build(t->nxt[1], vj, lim / 3); if (f) f &= build(t->nxt[2], vk, lim / 3); if (f) return 1; } FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) { *t = Tree(4, i, j, k, d); vector<int> vi, vj, vk; bool f = 1; for (int id : cur) { int pi = pos[id][i], pj = pos[id][j], pk = pos[id][k], pd = pos[id][d], cp = 6; for (int xp : {pi, pj, pk}) if (xp > pd) cp = min(cp, xp); if (cp == 6) cp = min({pi, pj, pk}); (pos[id][i] == cp ? vi : pos[id][j] == cp ? vj : vk).pb(id); if (max({vi.size(), vj.size(), vk.size()}) > lim) { f = 0; break; } } if (f) f &= build(t->nxt[0], vi, lim / 3); if (f) f &= build(t->nxt[1], vj, lim / 3); if (f) f &= build(t->nxt[2], vk, lim / 3); if (f) return 1; } delete(t); return 0; } void init(int T) { array<int, 6> a; iota(a.begin(), a.end(), 1); FOR (i, 0, MAX - 1) { P[i] = a; FOR (j, 0, 5) pos[i][a[j]] = j; next_permutation(a.begin(), a.end()); } vector<int> all(MAX); iota(all.begin(), all.end(), 0); build(root, all, 243); } void orderCoins() { vector<int> all(MAX); iota(all.begin(), all.end(), 0); Tree *cur = root; while (all.size() > 1) { int result; auto [ty, a, b, c, d] = cur->id(); if (ty == 1) result = getLightest(a, b, c); if (ty == 2) result = getHeaviest(a, b, c); if (ty == 3) result = getMedian(a, b, c); if (ty == 4) result = getNextLightest(a, b, c, d); vector<int> tmp; for (int id : all) { int pi = pos[id][a], pj = pos[id][b], pk = pos[id][c]; if (ty == 1 && min({pi, pj, pk}) == pos[id][result]) tmp.pb(id); if (ty == 2 && max({pi, pj, pk}) == pos[id][result]) tmp.pb(id); if (ty == 3 && pi + pj + pk - min({pi, pj, pk}) - max({pi, pj, pk}) == pos[id][result]) tmp.pb(id); if (ty == 4) { int mn = 6; for (int xp : {pi, pj, pk}) if (xp > pos[id][d]) mn = min(mn, xp); if (mn == 6) mn = min({pi, pj, pk}); if (mn == pos[id][result]) tmp.pb(id); } } all = tmp; cur = (result == a ? cur->nxt[0] : result == b ? cur->nxt[1] : cur->nxt[2]); } int ans[6]; FOR (i, 0, 5) ans[i] = P[all[0]][i]; answer(ans); }

Compilation message (stderr)

scales.cpp: In constructor 'Tree::Tree(int, int, int, int, int)':
scales.cpp:23:43: warning: declaration of 'd' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                                       ~~~~^~~~~
scales.cpp:20:22: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |                      ^
scales.cpp:23:36: warning: declaration of 'c' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                                ~~~~^
scales.cpp:20:19: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |                   ^
scales.cpp:23:29: warning: declaration of 'b' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                         ~~~~^
scales.cpp:20:16: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |                ^
scales.cpp:23:22: warning: declaration of 'a' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                  ~~~~^
scales.cpp:20:13: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |             ^
scales.cpp:23:14: warning: declaration of 'ty' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |          ~~~~^~
scales.cpp:20:9: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |         ^~
scales.cpp: In constructor 'Tree::Tree(int, int, int, int, int)':
scales.cpp:23:43: warning: declaration of 'd' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                                       ~~~~^~~~~
scales.cpp:20:22: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |                      ^
scales.cpp:23:36: warning: declaration of 'c' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                                ~~~~^
scales.cpp:20:19: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |                   ^
scales.cpp:23:29: warning: declaration of 'b' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                         ~~~~^
scales.cpp:20:16: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |                ^
scales.cpp:23:22: warning: declaration of 'a' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                  ~~~~^
scales.cpp:20:13: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |             ^
scales.cpp:23:14: warning: declaration of 'ty' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |          ~~~~^~
scales.cpp:20:9: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |         ^~
scales.cpp: In constructor 'Tree::Tree(int, int, int, int, int)':
scales.cpp:23:43: warning: declaration of 'd' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                                       ~~~~^~~~~
scales.cpp:20:22: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |                      ^
scales.cpp:23:36: warning: declaration of 'c' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                                ~~~~^
scales.cpp:20:19: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |                   ^
scales.cpp:23:29: warning: declaration of 'b' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                         ~~~~^
scales.cpp:20:16: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |                ^
scales.cpp:23:22: warning: declaration of 'a' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |                  ~~~~^
scales.cpp:20:13: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |             ^
scales.cpp:23:14: warning: declaration of 'ty' shadows a member of 'Tree' [-Wshadow]
   23 |     Tree(int ty, int a, int b, int c, int d = 0) : ty(ty), a(a), b(b), c(c), d(d) {}
      |          ~~~~^~
scales.cpp:20:9: note: shadowed declaration is here
   20 |     int ty, a, b, c, d;
      |         ^~
scales.cpp: In function 'bool build(Tree*&, std::vector<int>, int)':
scales.cpp:9:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:33:20: note: in expansion of macro 'FOR'
   33 |     FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
      |                    ^~~
scales.cpp:9:36: note: shadowed declaration is here
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:33:5: note: in expansion of macro 'FOR'
   33 |     FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
      |     ^~~
scales.cpp:9:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:33:34: note: in expansion of macro 'FOR'
   33 |     FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
      |                                  ^~~
scales.cpp:9:36: note: shadowed declaration is here
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:33:20: note: in expansion of macro 'FOR'
   33 |     FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
      |                    ^~~
scales.cpp:9:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:33:52: note: in expansion of macro 'FOR'
   33 |     FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
      |                                                    ^~~
scales.cpp:9:36: note: shadowed declaration is here
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:33:34: note: in expansion of macro 'FOR'
   33 |     FOR (ty, 1, 3) FOR (i, 1, 6) FOR (j, i + 1, 6) FOR (k, j + 1, 6) {
      |                                  ^~~
scales.cpp:43:56: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   43 |             if (max({vi.size(), vj.size(), vk.size()}) > lim) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
scales.cpp:9:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:53:19: note: in expansion of macro 'FOR'
   53 |     FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
      |                   ^~~
scales.cpp:9:36: note: shadowed declaration is here
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:53:5: note: in expansion of macro 'FOR'
   53 |     FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
      |     ^~~
scales.cpp:9:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:53:45: note: in expansion of macro 'FOR'
   53 |     FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
      |                                             ^~~
scales.cpp:9:36: note: shadowed declaration is here
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:53:19: note: in expansion of macro 'FOR'
   53 |     FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
      |                   ^~~
scales.cpp:9:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:53:75: note: in expansion of macro 'FOR'
   53 |     FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
      |                                                                           ^~~
scales.cpp:9:36: note: shadowed declaration is here
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:53:45: note: in expansion of macro 'FOR'
   53 |     FOR (d, 1, 6) FOR (i, 1, 6) if (i != d) FOR (j, i + 1, 6) if (j != d) FOR (k, j + 1, 6) if (k != d) {
      |                                             ^~~
scales.cpp:62:56: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   62 |             if (max({vi.size(), vj.size(), vk.size()}) > lim) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:9:36: warning: declaration of 'I' shadows a previous local [-Wshadow]
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:81:9: note: in expansion of macro 'FOR'
   81 |         FOR (j, 0, 5) pos[i][a[j]] = j;
      |         ^~~
scales.cpp:9:36: note: shadowed declaration is here
    9 | #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
      |                                    ^
scales.cpp:79:5: note: in expansion of macro 'FOR'
   79 |     FOR (i, 0, MAX - 1) {
      |     ^~~
scales.cpp:76:15: warning: unused parameter 'T' [-Wunused-parameter]
   76 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:114:56: warning: 'result' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |         cur = (result == a ? cur->nxt[0] : result == b ? cur->nxt[1] : cur->nxt[2]);
      |                                            ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask 1100 / 100

#	Verdict	Execution time	Memory	Grader output
Fetching results...