Submission #588132

#	Time	Username	Problem	Language	Result	Execution time	Memory
588132		MohamedFaresNebili	Scales (IOI15_scales)	C++14	100 / 100	96 ms	428 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

#include <bits/stdc++.h> #include "scales.h" /// #pragma GCC optimize ("Ofast") /// #pragma GCC target ("avx2") /// #pragma GCC optimize("unroll-loops") using namespace std; using ll = long long; using ii = pair<ll, ll>; using vi = vector<int>; #define ff first #define ss second #define pb push_back #define all(x) (x).begin(), (x).end() #define lb lower_bound const int MOD = 1000 * 1000 * 1000 + 7; struct node{ int A, B, C, D, T; node() {}; node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {}; }; vector<vector<int>> V; vector<node> Q; void init(int T) { vector<int> A(6); for(int l = 0; l < 6; l++) A[l] = l; do { V.push_back(A); } while(next_permutation(A.begin(), A.end())); for(int l = 0; l < 6; l++) for(int i = l + 1; i < 6; i++) for(int j = i + 1; j < 6; j++) Q.push_back({l, i, j, 0, 0}), Q.push_back({l, i, j, 0, 1}), Q.push_back({l, i, j, 0, 2}); for(int k = 0; k < 6; k++) for(int l = 0; l < 6; l++) for(int i = l + 1; i < 6; i++) for(int j = i + 1; j < 6; j++) { if(k == l || k == i || k == j) continue; Q.push_back({l, i, j, k, 3}); } return; } int med(int A, int B, int C) { if(max({A, B, C}) != A && min({A, B, C}) != A) return A; if(max({A, B, C}) != B && min({A, B, C}) != B) return B; if(max({A, B, C}) != C && min({A, B, C}) != C) return C; } int nextL(int A, int B, int C, int D) { int res = 1e9 + 7; if(A > D) res = min(res, A); if(B > D) res = min(res, B); if(C > D) res = min(res, C); if(res == 1e9 + 7) res = min({A, B, C}); return res; } void orderCoins(void) { vector<vector<int>> perm = V; while(perm.size() > 1) { node query; int best = 1e9 + 7; for(auto u : Q) { if(u.T == 0) { int A = 0, B = 0, C = 0; for(auto v : perm) { if(max({v[u.A], v[u.B], v[u.C]}) == v[u.A]) A++; if(max({v[u.A], v[u.B], v[u.C]}) == v[u.B]) B++; if(max({v[u.A], v[u.B], v[u.C]}) == v[u.C]) C++; } A = max({A, B, C}); if(best >= A) best = A, query = u; } if(u.T == 1) { int A = 0, B = 0, C = 0; for(auto v : perm) { if(min({v[u.A], v[u.B], v[u.C]}) == v[u.A]) A++; if(min({v[u.A], v[u.B], v[u.C]}) == v[u.B]) B++; if(min({v[u.A], v[u.B], v[u.C]}) == v[u.C]) C++; } A = max({A, B, C}); if(best >= A) best = A, query = u; } if(u.T == 2) { int A = 0, B = 0, C = 0; for(auto v : perm) { if(med(v[u.A], v[u.B], v[u.C]) == v[u.A]) A++; if(med(v[u.A], v[u.B], v[u.C]) == v[u.B]) B++; if(med(v[u.A], v[u.B], v[u.C]) == v[u.C]) C++; } A = max({A, B, C}); if(best >= A) best = A, query = u; } if(u.T == 3) { int A = 0, B = 0, C = 0; for(auto v : perm) { if(nextL(v[u.A], v[u.B], v[u.C], v[u.D]) == v[u.A]) A++; if(nextL(v[u.A], v[u.B], v[u.C], v[u.D]) == v[u.B]) B++; if(nextL(v[u.A], v[u.B], v[u.C], v[u.D]) == v[u.C]) C++; } A = max({A, B, C}); if(best >= A) best = A, query = u; } } vector<vector<int>> P; if(query.T == 0) { int K = getHeaviest(query.A + 1, query.B + 1, query.C + 1) - 1; for(auto u : perm) { if(max({u[query.A], u[query.B], u[query.C]}) == u[K]) P.pb(u); } } if(query.T == 1) { int K = getLightest(query.A + 1, query.B + 1, query.C + 1) - 1; for(auto u : perm) { if(min({u[query.A], u[query.B], u[query.C]}) == u[K]) P.pb(u); } } if(query.T == 2) { int K = getMedian(query.A + 1, query.B + 1, query.C + 1) - 1; for(auto u : perm) { if(med(u[query.A], u[query.B], u[query.C]) == u[K]) P.pb(u); } } if(query.T == 3) { int K = getNextLightest(query.A + 1, query.B + 1, query.C + 1, query.D + 1) - 1; for(auto u : perm) { if(nextL(u[query.A], u[query.B], u[query.C], u[query.D]) == u[K]) P.pb(u); } } swap(P, perm); } int res[6]; for(int l = 0; l < 6; l++) res[perm[0][l]] = l + 1; answer(res); }

Compilation message (stderr)

scales.cpp: In constructor 'node::node(int, int, int, int, int)':
scales.cpp:24:58: warning: declaration of 'T' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                                                      ~~~~^
scales.cpp:22:37: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                                     ^
scales.cpp:24:51: warning: declaration of 'D' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                                               ~~~~^
scales.cpp:22:34: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                                  ^
scales.cpp:24:44: warning: declaration of 'C' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                                        ~~~~^
scales.cpp:22:31: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                               ^
scales.cpp:24:37: warning: declaration of 'B' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                                 ~~~~^
scales.cpp:22:28: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                            ^
scales.cpp:24:30: warning: declaration of 'A' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                          ~~~~^
scales.cpp:22:25: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                         ^
scales.cpp: In constructor 'node::node(int, int, int, int, int)':
scales.cpp:24:58: warning: declaration of 'T' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                                                      ~~~~^
scales.cpp:22:37: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                                     ^
scales.cpp:24:51: warning: declaration of 'D' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                                               ~~~~^
scales.cpp:22:34: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                                  ^
scales.cpp:24:44: warning: declaration of 'C' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                                        ~~~~^
scales.cpp:22:31: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                               ^
scales.cpp:24:37: warning: declaration of 'B' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                                 ~~~~^
scales.cpp:22:28: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                            ^
scales.cpp:24:30: warning: declaration of 'A' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                          ~~~~^
scales.cpp:22:25: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                         ^
scales.cpp: In constructor 'node::node(int, int, int, int, int)':
scales.cpp:24:58: warning: declaration of 'T' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                                                      ~~~~^
scales.cpp:22:37: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                                     ^
scales.cpp:24:51: warning: declaration of 'D' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                                               ~~~~^
scales.cpp:22:34: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                                  ^
scales.cpp:24:44: warning: declaration of 'C' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                                        ~~~~^
scales.cpp:22:31: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                               ^
scales.cpp:24:37: warning: declaration of 'B' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                                 ~~~~^
scales.cpp:22:28: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                            ^
scales.cpp:24:30: warning: declaration of 'A' shadows a member of 'node' [-Wshadow]
   24 |                     node(int A, int B, int C, int D, int T): A(A), B(B), C(C), D(D), T(T) {};
      |                          ~~~~^
scales.cpp:22:25: note: shadowed declaration is here
   22 |                     int A, B, C, D, T;
      |                         ^
scales.cpp: In function 'void init(int)':
scales.cpp:30:31: warning: unused parameter 'T' [-Wunused-parameter]
   30 |                 void init(int T) {
      |                           ~~~~^
scales.cpp: In function 'int med(int, int, int)':
scales.cpp:55:17: warning: control reaches end of non-void function [-Wreturn-type]
   55 |                 }
      |                 ^
scales.cpp: In function 'void orderCoins()':
scales.cpp:117:48: warning: 'query.node::A' may be used uninitialized in this function [-Wmaybe-uninitialized]
  117 |                             int K = getHeaviest(query.A + 1, query.B + 1, query.C + 1) - 1;
      |                                     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:117:48: warning: 'query.node::C' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:117:48: warning: 'query.node::B' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:135:52: warning: 'query.node::D' may be used uninitialized in this function [-Wmaybe-uninitialized]
  135 |                             int K = getNextLightest(query.A + 1, query.B + 1, query.C + 1, query.D + 1) - 1;
      |                                     ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:128:25: warning: 'query.node::T' may be used uninitialized in this function [-Wmaybe-uninitialized]
  128 |                         if(query.T == 2) {
      |                         ^~

Subtask 1100 / 100

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