Submission #729587

#	Time	Username	Problem	Language	Result	Execution time	Memory
729587		Vu_CG_Coder	Scales (IOI15_scales)	C++14	71.43 / 100	31 ms	468 KiB

scales

/* [Author : Hoang Duy Vu] - THPT Chuyen Nguyen Du    */
//#pragma GCC optimize(" unroll-loops")
//#pragma gcc optimize("Ofast")
//#pragma GCC optimization("Ofast")
//#pragma optimize(Ofast)
#include "scales.h"
#include <bits/stdc++.h>
#define All(x) (x).begin(),(x).end()
#define ll long long
#define C make_pair
#define fi first
#define se second
#define two second.first
#define thr second.second
#define TASK "txt"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) {
    if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) {
    if (res > val) { res = val; return true; } return false; }
 
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int LOG = 20;
const int INF = 1e9 + 7;
const ll LNF = 1e18 + 7;
const int mod = 1e9 + 7;
const int N = 10;
 
//unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
//mt19937 Rand(seed);
 
struct node
{
    int a , b , c , id;
    node() {}
    node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
};
 
vector <vector<int> > f[11];
vector <vector<int> > p;
vector <node> local;
vector <pair<vector<int>,int> > value;
int id = 0;
int cnt;
int val[N];
 
// int getLightest(int a , int b , int c)
// {
//     for (int i = 0 ; i < 5 ; i++)
//     if (val[i] == a || val[i] == b || val[i] == c) return val[i];
// }
 
// int getHeaviest(int a , int b , int c)
// {
//     for (int i = 5 ; i >= 0 ; i--)
//     if (val[i] == a || val[i] == b || val[i] == c) return val[i];
// }
 
// int getMedian(int a , int b , int c)
// {
//     int d = 0;
//     for (int i = 0 ; i < 5 ; i++)
//     if (val[i] == a || val[i] == b || val[i] == c)
//     {
//         d++;
//         if (d == 2) return val[i];
//     }
// }
 
// void answer(int x[]) {
 
//     cout << id << " :";
//     for (int i = 0 ; i < 6 ; i++) cout << x[i] << " ";
//     cout << "\n";
// }
 
void init(int T) {
}
 
int light(int pos , int a , int b , int c,int o)
{
    vector <int> x;
    x.push_back(a);
    x.push_back(b);
    x.push_back(c);
    int d = 0;
 
    for (int i = 0; i < f[id - 1].size() ; i++)
    if (min(f[id - 1][i][a],min(f[id - 1][i][b],f[id - 1][i][c])) == f[id - 1][i][x[pos]])
    {
        d++;
        if (o) f[id].push_back(f[id - 1][i]);
    }
 
    return d;
}
 
int Heaviest(int pos , int a , int b , int c,int o)
{
    vector <int> x;
    x.push_back(a);
    x.push_back(b);
    x.push_back(c);
    int d = 0;
 
    for (int i = 0; i < f[id - 1].size() ; i++)
    if (max(f[id - 1][i][a],max(f[id - 1][i][b],f[id - 1][i][c])) == f[id - 1][i][x[pos]])
    {
        d++;
        if (o) f[id].push_back(f[id - 1][i]);
    }
 
    return d;
}
 
int Median(int pos , int a , int b , int c,int o)
{
    vector <int> x;
    x.push_back(a);
    x.push_back(b);
    x.push_back(c);
    int d = 0;
 
    for (int i = 0; i < f[id - 1].size() ; i++)
    if (max(f[id - 1][i][a],max(f[id - 1][i][b],f[id - 1][i][c])) != f[id - 1][i][x[pos]] &&
        min(f[id - 1][i][a],min(f[id - 1][i][b],f[id - 1][i][c])) != f[id - 1][i][x[pos]])
    {
        d++;
        if (o) f[id].push_back(f[id - 1][i]);
    }
 
    return d;
}
 
void orderCoins() {
    int W[] = {1,2,3,4,5,6};
 
    vector <int> k;
    for (int i = 1 ; i <= 6 ; i++) k.push_back(i);
    for (int i = 0 ; i < 11 ; i++) f[i].clear();
 
    cnt = 0;
    do
    {
        vector <int> x;
        x.push_back(0);
        for (int i = 0; i < 6 ; i++) x.push_back(k[i]);
        f[0].push_back(x);
    } while (next_permutation(All(k)));
 
    id = 0;
    while (true)
    {
        int d = 0;
        id++;
        p.clear();
        int cntpos = 0;
        local.clear();
        value.clear();
        
        for (int a = 1 ; a <= 6 ; a++)
            for (int b = a + 1; b <= 6 ; b++)
                for (int c = b + 1; c <= 6 ; c++) 
        {
            vector <int> x;
            local.push_back(node(a,b,c,0));
            x.push_back(light(0,a,b,c,0));
            x.push_back(light(1,a,b,c,0));
            x.push_back(light(2,a,b,c,0));
            value.push_back(C(x,cntpos++));
 
            x.clear();
            local.push_back(node(a,b,c,1));
            x.push_back(Heaviest(0,a,b,c,0));
            x.push_back(Heaviest(1,a,b,c,0));
            x.push_back(Heaviest(2,a,b,c,0));
            value.push_back(C(x,cntpos++));
 
            x.clear();
            local.push_back(node(a,b,c,2));
            x.push_back(Median(0,a,b,c,0));
            x.push_back(Median(1,a,b,c,0));
            x.push_back(Median(2,a,b,c,0));
            value.push_back(C(x,cntpos++));
        }
 
        for (int i = 0 ; i < cntpos ; i++) sort(All(value[i].fi),greater<int>());
        sort(All(value));
 
        int vt = value[0].se;
        int a = local[vt].a;
        int b = local[vt].b;
        int c = local[vt].c;
 
        if (local[vt].id == 0) {
            int ioi = getLightest(a,b,c);
 
            if (ioi == a) light(0,a,b,c,1);
            if (ioi == b) light(1,a,b,c,1);
            if (ioi == c) light(2,a,b,c,1);
        }
 
        if (local[vt].id == 1) {
            int ioi = getHeaviest(a,b,c);
 
            if (ioi == a) Heaviest(0,a,b,c,1);
            if (ioi == b) Heaviest(1,a,b,c,1);
            if (ioi == c) Heaviest(2,a,b,c,1);
        }
 
        if (local[vt].id == 2) {
            int ioi = getMedian(a,b,c);
 
            if (ioi == a) Median(0,a,b,c,1);
            if (ioi == b) Median(1,a,b,c,1);
            if (ioi == c) Median(2,a,b,c,1);
        }
 
        if (f[id].size() == 1) break ;
    }
 
    for (int i = 0 ; i < 6 ; i++) 
    {
        for (int j = 1 ; j <= 6 ; j++) if (f[id][0][j] == i + 1) W[i] = j;
    }
    
 
    answer(W);
}
 
// int main()
// {
//     ios_base::sync_with_stdio(0);
//     cin.tie(NULL); cout.tie(NULL);
//     if(fopen(TASK".inp", "r")){
//     freopen(TASK".inp","r",stdin);
//     freopen(TASK".out","w",stdout);
//     }
 
//   //  int b[6] = {0};
//     for (int i = 0 ; i < 6 ; i++) val[i] = i + 1;
//     do
//     {
//         for (int i = 0 ; i < 6 ; i++) cout << val[i] << " ";
//         cout << "\n";
//         orderCoins();
//        // break;
//     } while (next_permutation(val,val + 6));
    
    
 
 
//     return 0;
// }

Compilation message (stderr)

scales.cpp: In constructor 'node::node(int, int, int, int)':
scales.cpp:37:38: warning: declaration of 'id' shadows a member of 'node' [-Wshadow]
   37 |     node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
      |                                  ~~~~^~
scales.cpp:35:21: note: shadowed declaration is here
   35 |     int a , b , c , id;
      |                     ^~
scales.cpp:37:30: warning: declaration of 'c' shadows a member of 'node' [-Wshadow]
   37 |     node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
      |                          ~~~~^
scales.cpp:35:17: note: shadowed declaration is here
   35 |     int a , b , c , id;
      |                 ^
scales.cpp:37:22: warning: declaration of 'b' shadows a member of 'node' [-Wshadow]
   37 |     node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
      |                  ~~~~^
scales.cpp:35:13: note: shadowed declaration is here
   35 |     int a , b , c , id;
      |             ^
scales.cpp:37:14: warning: declaration of 'a' shadows a member of 'node' [-Wshadow]
   37 |     node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
      |          ~~~~^
scales.cpp:35:9: note: shadowed declaration is here
   35 |     int a , b , c , id;
      |         ^
scales.cpp: In constructor 'node::node(int, int, int, int)':
scales.cpp:37:38: warning: declaration of 'id' shadows a member of 'node' [-Wshadow]
   37 |     node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
      |                                  ~~~~^~
scales.cpp:35:21: note: shadowed declaration is here
   35 |     int a , b , c , id;
      |                     ^~
scales.cpp:37:30: warning: declaration of 'c' shadows a member of 'node' [-Wshadow]
   37 |     node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
      |                          ~~~~^
scales.cpp:35:17: note: shadowed declaration is here
   35 |     int a , b , c , id;
      |                 ^
scales.cpp:37:22: warning: declaration of 'b' shadows a member of 'node' [-Wshadow]
   37 |     node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
      |                  ~~~~^
scales.cpp:35:13: note: shadowed declaration is here
   35 |     int a , b , c , id;
      |             ^
scales.cpp:37:14: warning: declaration of 'a' shadows a member of 'node' [-Wshadow]
   37 |     node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
      |          ~~~~^
scales.cpp:35:9: note: shadowed declaration is here
   35 |     int a , b , c , id;
      |         ^
scales.cpp: In constructor 'node::node(int, int, int, int)':
scales.cpp:37:38: warning: declaration of 'id' shadows a member of 'node' [-Wshadow]
   37 |     node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
      |                                  ~~~~^~
scales.cpp:35:21: note: shadowed declaration is here
   35 |     int a , b , c , id;
      |                     ^~
scales.cpp:37:30: warning: declaration of 'c' shadows a member of 'node' [-Wshadow]
   37 |     node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
      |                          ~~~~^
scales.cpp:35:17: note: shadowed declaration is here
   35 |     int a , b , c , id;
      |                 ^
scales.cpp:37:22: warning: declaration of 'b' shadows a member of 'node' [-Wshadow]
   37 |     node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
      |                  ~~~~^
scales.cpp:35:13: note: shadowed declaration is here
   35 |     int a , b , c , id;
      |             ^
scales.cpp:37:14: warning: declaration of 'a' shadows a member of 'node' [-Wshadow]
   37 |     node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
      |          ~~~~^
scales.cpp:35:9: note: shadowed declaration is here
   35 |     int a , b , c , id;
      |         ^
scales.cpp: In function 'void init(int)':
scales.cpp:78:15: warning: unused parameter 'T' [-Wunused-parameter]
   78 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'int light(int, int, int, int, int)':
scales.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < f[id - 1].size() ; i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'int Heaviest(int, int, int, int, int)':
scales.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for (int i = 0; i < f[id - 1].size() ; i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'int Median(int, int, int, int, int)':
scales.cpp:125:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for (int i = 0; i < f[id - 1].size() ; i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:155:13: warning: unused variable 'd' [-Wunused-variable]
  155 |         int d = 0;
      |             ^

• Subtask 1: 71.428571 / 100