Submission #1073570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073570		ArthuroWich	Scales (IOI15_scales)	C++17	0 / 100	1099 ms	852 KiB

scales

#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> removeheavy(vector<vector<int>> p, int A, int B, int C, int st) {
    int a, b, c;
    if (st == -1) {
        st = getHeaviest(A, B, C);
    }
    if (st == A) {
        c = A;
        a = B;
        b = C;
    } else if (st == B) {
        c = B;
        a = C;
        b = A;
    } else if (st == C) {
        c = C;
        a = A;
        b = B;
    }
    vector<vector<int>> t;
    for (auto x : p) {
        if (find(x.begin(), x.end(), a)-x.begin() < find(x.begin(), x.end(), c)-x.begin() && find(x.begin(), x.end(), b)-x.begin() < find(x.begin(), x.end(), c)-x.begin()) {
            t.push_back(x);
        }
    }
    return t;
}
vector<vector<int>> removelight(vector<vector<int>> p, int A, int B, int C, int st) {
    int a, b, c;
    if (st == -1) {
        st = getLightest(A, B, C);
    }
    if (st == A) {
        c = A;
        a = B;
        b = C;
    } else if (st == B) {
        c = B;
        a = C;
        b = A;
    } else if (st == C) {
        c = C;
        a = A;
        b = B;
    }
    vector<vector<int>> t;
    for (auto x : p) {
        if (find(x.begin(), x.end(), a)-x.begin() > find(x.begin(), x.end(), c)-x.begin() && find(x.begin(), x.end(), b)-x.begin() > find(x.begin(), x.end(), c)-x.begin()) {
            t.push_back(x);
        }
    }
    return t;
}
vector<vector<int>> removemedian(vector<vector<int>> p, int A, int B, int C, int st) {
    int a, b, c;
    if (st == -1) {
        st = getMedian(A, B, C);
    }
    if (st == A) {
        c = A;
        a = B;
        b = C;
    } else if (st == B) {
        c = B;
        a = C;
        b = A;
    } else if (st == C) {
        c = C;
        a = A;
        b = B;
    }
    vector<vector<int>> t;
    for (auto x : p) {
        if (!(find(x.begin(), x.end(), a)-x.begin() > find(x.begin(), x.end(), c)-x.begin() && find(x.begin(), x.end(), b)-x.begin() > find(x.begin(), x.end(), c)-x.begin())&&!(find(x.begin(), x.end(), a)-x.begin() < find(x.begin(), x.end(), c)-x.begin() && find(x.begin(), x.end(), b)-x.begin() < find(x.begin(), x.end(), c)-x.begin())) {
            t.push_back(x);
        }
    }
    return t;
}
vector<tuple<int, int, int, int>> opt;
map<vector<tuple<int, int, int, int>>, int> op;
vector<int> perm = {6, 5, 4, 3, 2, 1}, lim = {729, 243, 81, 27, 9, 3, 1};
int heavy(int a, int b, int c) {
    int ind1 = find(perm.begin(), perm.end(), a) - perm.begin(), ind2 = find(perm.begin(), perm.end(), b) - perm.begin(), ind3 = find(perm.begin(), perm.end(), c) - perm.begin();
    vector<pair<int, int>> v = {{ind1, a}, {ind2, b}, {ind3, c}};
    sort(v.begin(), v.end());
    return v[2].second;
}
int light(int a, int b, int c) {
    int ind1 = find(perm.begin(), perm.end(), a) - perm.begin(), ind2 = find(perm.begin(), perm.end(), b) - perm.begin(), ind3 = find(perm.begin(), perm.end(), c) - perm.begin();
    vector<pair<int, int>> v = {{ind1, a}, {ind2, b}, {ind3, c}};
    sort(v.begin(), v.end());
    return v[0].second;
}
int median(int a, int b, int c) {
    int ind1 = find(perm.begin(), perm.end(), a) - perm.begin(), ind2 = find(perm.begin(), perm.end(), b) - perm.begin(), ind3 = find(perm.begin(), perm.end(), c) - perm.begin();
    vector<pair<int, int>> v = {{ind1, a}, {ind2, b}, {ind3, c}};
    sort(v.begin(), v.end());
    return v[1].second;
}
void dfs(vector<tuple<int, int, int, int>> ord, vector<vector<int>> p) {
    if (p.size() == 0) {
        return;
    }
    if (opt.size() == 6) {
        return;
    }
    if (p.size() > lim[ord.size()]) {
        return;
    }
    if (ord.size() == 6) {
        if (p.size() == 1) {
            opt = ord;
        }
        return;
    }
    for (int i = 1; i <= 6; i++) {
        for (int j = i+1; j <= 6; j++) {
            for (int k = j+1; k <= 6; k++) {
                ord.push_back({i, j, k, 0});
                dfs(ord, removeheavy(p, i, j, k, heavy(i, j, k)));
                ord.pop_back();
                ord.push_back({i, j, k, 1});
                dfs(ord, removelight(p, i, j, k, light(i, j, k)));
                ord.pop_back();
                ord.push_back({i, j, k, 2});
                dfs(ord, removemedian(p, i, j, k, median(i, j, k)));
                ord.pop_back();
            }
        }
    }
}
void init(int T) {
    vector<int> a = {1, 2, 3, 4, 5, 6};
    vector<vector<int>> p;
    int v = 0;
    do {
        p.push_back(a);
    } while (next_permutation(a.begin(), a.end()));
    for (auto x : p) {
        perm = x;
        dfs({}, p);
        op[opt]++;
        opt = {};
    }
    for (auto [i, co] : op) {
        if (co > v) {
            opt = i;
            v = co;
        }
    }
}
void orderCoins() {
    int W[6];
    vector<int> a = {1, 2, 3, 4, 5, 6};
    vector<vector<int>> p;
    do {
        p.push_back(a);
    } while (next_permutation(a.begin(), a.end()));
    for (auto [i, j, k, op] : opt) {
        if (op == 0) {
            p = removeheavy(p, i, j, k, -1);
        } else if (op == 1) {
            p = removelight(p, i, j, k, -1);
        } else if (op == 2) {
            p = removemedian(p, i, j, k, -1);
        }
    }
    for (int i = 0; i < 6; i++) {
        W[i] = p[0][i];
    }
    answer(W);
}

Compilation message (stderr)

scales.cpp: In function 'int heavy(int, int, int)':
scales.cpp:86:50: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   86 |     int ind1 = find(perm.begin(), perm.end(), a) - perm.begin(), ind2 = find(perm.begin(), perm.end(), b) - perm.begin(), ind3 = find(perm.begin(), perm.end(), c) - perm.begin();
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:86:107: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   86 |     int ind1 = find(perm.begin(), perm.end(), a) - perm.begin(), ind2 = find(perm.begin(), perm.end(), b) - perm.begin(), ind3 = find(perm.begin(), perm.end(), c) - perm.begin();
      |                                                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:86:164: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   86 |     int ind1 = find(perm.begin(), perm.end(), a) - perm.begin(), ind2 = find(perm.begin(), perm.end(), b) - perm.begin(), ind3 = find(perm.begin(), perm.end(), c) - perm.begin();
      |                                                                                                                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp: In function 'int light(int, int, int)':
scales.cpp:92:50: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   92 |     int ind1 = find(perm.begin(), perm.end(), a) - perm.begin(), ind2 = find(perm.begin(), perm.end(), b) - perm.begin(), ind3 = find(perm.begin(), perm.end(), c) - perm.begin();
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:92:107: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   92 |     int ind1 = find(perm.begin(), perm.end(), a) - perm.begin(), ind2 = find(perm.begin(), perm.end(), b) - perm.begin(), ind3 = find(perm.begin(), perm.end(), c) - perm.begin();
      |                                                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:92:164: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   92 |     int ind1 = find(perm.begin(), perm.end(), a) - perm.begin(), ind2 = find(perm.begin(), perm.end(), b) - perm.begin(), ind3 = find(perm.begin(), perm.end(), c) - perm.begin();
      |                                                                                                                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp: In function 'int median(int, int, int)':
scales.cpp:98:50: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   98 |     int ind1 = find(perm.begin(), perm.end(), a) - perm.begin(), ind2 = find(perm.begin(), perm.end(), b) - perm.begin(), ind3 = find(perm.begin(), perm.end(), c) - perm.begin();
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:98:107: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   98 |     int ind1 = find(perm.begin(), perm.end(), a) - perm.begin(), ind2 = find(perm.begin(), perm.end(), b) - perm.begin(), ind3 = find(perm.begin(), perm.end(), c) - perm.begin();
      |                                                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:98:164: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   98 |     int ind1 = find(perm.begin(), perm.end(), a) - perm.begin(), ind2 = find(perm.begin(), perm.end(), b) - perm.begin(), ind3 = find(perm.begin(), perm.end(), c) - perm.begin();
      |                                                                                                                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
scales.cpp: In function 'void dfs(std::vector<std::tuple<int, int, int, int> >, std::vector<std::vector<int> >)':
scales.cpp:110:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
  110 |     if (p.size() > lim[ord.size()]) {
scales.cpp: In function 'void init(int)':
scales.cpp:135:15: warning: unused parameter 'T' [-Wunused-parameter]
  135 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:162:25: warning: declaration of 'op' shadows a global declaration [-Wshadow]
  162 |     for (auto [i, j, k, op] : opt) {
      |                         ^~
scales.cpp:83:45: note: shadowed declaration is here
   83 | map<vector<tuple<int, int, int, int>>, int> op;
      |                                             ^~

• Subtask 1: 0 / 100