Submission #588121

#	Time	Username	Problem	Language	Result	Execution time	Memory
588121		MohamedFaresNebili	Scales (IOI15_scales)	C++14	0 / 100	7 ms	648 KiB

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

• Subtask 1: 0 / 100