Submission #433465

#	Time	Username	Problem	Language	Result	Execution time	Memory
433465		Tangent	Scales (IOI15_scales)	C++17	71.73 / 100	4 ms	308 KiB

scales

#include "scales.h"
#include "bits/stdc++.h"
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
 
#define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++)
#define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()

inline int gm(int A, int B, int C) {
    if (B < A && A < C)
        return 0;

    if (C < A && A < B)
        return 0;

    if (A < B && B < C)
        return 1;

    if (C < B && B < A)
        return 1;

    return 2;
}

inline int gh(int A, int B, int C) {
    if (A > B && A > C)
        return 0;

    if (B > A && B > C)
        return 1;
    return 2;
}

inline int gl(int A, int B, int C) {
    if (A < B && A < C)
        return 0;
    
    if (B < A && B < C)
        return 1;

    return 2;
}

inline int gnl(int A, int B, int C, int D) {
    int allLess = 1;
    if (A > D || B > D || C > D)
        allLess = 0;

    if (allLess == 1) {
        if (A < B && A < C)
            return 0;
    
        if (B < A && B < C)
            return 1;

        return 2;
    }

    if (A > D) {
        if ((A < B || B < D) && (A < C || C < D))
            return 0;
    }

    if (B > D) {
        if ((B < A || A < D) && (B < C || C < D))
            return 1;
    }

    return 2;
}

const vvii combis = {{0, 1, 2}, {0, 1, 3}, {0, 1, 4}, {0, 1, 5}, {0, 2, 3}, {0, 2, 4}, {0, 2, 5}, {0, 3, 4}, {0, 3, 5}, {0, 4, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}};

void init(int T) {
}

void orderCoins() {
    vvii curr;
    vii x = {1, 2, 3, 4, 5, 6};
    int a = getLightest(1, 2, 3) - 1, b = getHeaviest(4, 5, 6) - 4;
    do {
        if (gl(x[0], x[1], x[2]) == a && gh(x[3], x[4], x[5]) == b) {
            curr.emplace_back(x);
        }
    } while(next_permutation(all(x)));
    
    while (curr.size() > 1) {
        int bmax = curr.size();
        int bc = -1, bt = -1;

        rep(i, combis.size()) {
            auto &combi = combis[i];
            vii cnts(3);
            forin(p, curr) {
                cnts[gl(p[combi[0]], p[combi[1]], p[combi[2]])]++;
            }
            int cmax = max(cnts[0], max(cnts[1], cnts[2]));
            if (cmax < bmax) {
                bmax = cmax;
                bc = i;
                bt = 0;
            }
            cnts.assign(3, 0);
            forin(p, curr) {
                cnts[gm(p[combi[0]], p[combi[1]], p[combi[2]])]++;
            }
            cmax = max(cnts[0], max(cnts[1], cnts[2]));
            if (cmax < bmax) {
                bmax = cmax;
                bc = i;
                bt = 1;
            }
            cnts.assign(3, 0);
            forin(p, curr) {
                cnts[gh(p[combi[0]], p[combi[1]], p[combi[2]])]++;
            }
            cmax = max(cnts[0], max(cnts[1], cnts[2]));
            if (cmax < bmax) {
                bmax = cmax;
                bc = i;
                bt = 2;
            }
            cnts.assign(3, 0);
            forin(p, curr) {
                cnts[gnl(p[combi[0]], p[combi[1]], p[combi[2]], p[combis[19 - i][0]])]++;
            }
            cmax = max(cnts[0], max(cnts[1], cnts[2]));
            if (cmax < bmax) {
                bmax = cmax;
                bc = i;
                bt = 3;
            }
            cnts.assign(3, 0);
            forin(p, curr) {
                cnts[gnl(p[combi[0]], p[combi[1]], p[combi[2]], p[combis[19 - i][1]])]++;
            }
            cmax = max(cnts[0], max(cnts[1], cnts[2]));
            if (cmax < bmax) {
                bmax = cmax;
                bc = i;
                bt = 4;
            }
            cnts.assign(3, 0);
            forin(p, curr) {
                cnts[gnl(p[combi[0]], p[combi[1]], p[combi[2]], p[combis[19 - i][2]])]++;
            }
            cmax = max(cnts[0], max(cnts[1], cnts[2]));
            if (cmax < bmax) {
                bmax = cmax;
                bc = i;
                bt = 5;
            }
        }

        vvii ncurr;
        auto combi = combis[bc];
        if (bt == 0) {
            int ans = getLightest(combi[0] + 1, combi[1] + 1, combi[2] + 1);
            if (ans == combi[0] + 1) {
                ans = 0;
            } else if (ans == combi[1] + 1) {
                ans = 1;
            } else {
                ans = 2;
            }
            forin(p, curr) {
                if (gl(p[combi[0]], p[combi[1]], p[combi[2]]) == ans) {
                    ncurr.emplace_back(p);
                }
            }
        } else if (bt == 1) {
            int ans = getMedian(combi[0] + 1, combi[1] + 1, combi[2] + 1);
            if (ans == combi[0] + 1) {
                ans = 0;
            } else if (ans == combi[1] + 1) {
                ans = 1;
            } else {
                ans = 2;
            }
            forin(p, curr) {
                if (gm(p[combi[0]], p[combi[1]], p[combi[2]]) == ans) {
                    ncurr.emplace_back(p);
                }
            }
        } else if (bt == 2) {
            int ans = getHeaviest(combi[0] + 1, combi[1] + 1, combi[2] + 1);
            if (ans == combi[0] + 1) {
                ans = 0;
            } else if (ans == combi[1] + 1) {
                ans = 1;
            } else {
                ans = 2;
            }
            forin(p, curr) {
                if (gh(p[combi[0]], p[combi[1]], p[combi[2]]) == ans) {
                    ncurr.emplace_back(p);
                }
            }
        } else {
            int d = combis[19 - bc][bt - 3];
            int ans = getNextLightest(combi[0] + 1, combi[1] + 1, combi[2] + 1, d + 1);
            if (ans == combi[0] + 1) {
                ans = 0;
            } else if (ans == combi[1] + 1) {
                ans = 1;
            } else {
                ans = 2;
            }
            forin(p, curr) {
                if (gnl(p[combi[0]], p[combi[1]], p[combi[2]], p[d]) == ans) {
                    ncurr.emplace_back(p);
                }
            }
        }
        curr = move(ncurr);
    }
    int res[] = {0, 0, 0, 0, 0, 0};
    rep(i, 6) {
        res[curr[0][i] - 1] = i + 1;
    }

    answer(res);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:89:15: warning: unused parameter 'T' [-Wunused-parameter]
   89 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:103:29: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  103 |         int bmax = curr.size();
      |                    ~~~~~~~~~^~
scales.cpp:115:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  115 |                 bc = i;
      |                      ^
scales.cpp:125:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  125 |                 bc = i;
      |                      ^
scales.cpp:135:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  135 |                 bc = i;
      |                      ^
scales.cpp:145:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  145 |                 bc = i;
      |                      ^
scales.cpp:155:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  155 |                 bc = i;
      |                      ^
scales.cpp:165:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  165 |                 bc = i;
      |                      ^
scales.cpp:234:33: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  234 |         res[curr[0][i] - 1] = i + 1;
      |                               ~~^~~

• Subtask 1: 71.72619 / 100