제출 #1037305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1037305		Zicrus	저울 (IOI15_scales)	C++17	71.43 / 100	123 ms	596 KiB

scales

#include <bits/stdc++.h>
#include "scales.h"
using namespace std;

typedef long long ll;

vector<vector<int>> perms(720);

void init(int T) {
    for (int i = 0; i < 720; i++) {
        perms[i] = {1, 2, 3, 4, 5, 6};
        swap(perms[i][0], perms[i][0 + ((i) % 6)]);
        swap(perms[i][1], perms[i][1 + ((i/6) % 5)]);
        swap(perms[i][2], perms[i][2 + ((i/6/5) % 4)]);
        swap(perms[i][3], perms[i][3 + ((i/6/5/4) % 3)]);
        swap(perms[i][4], perms[i][4 + ((i/6/5/4/3) % 2)]);
    }
}

int maxPossAfterLow(vector<bool> &poss, int a, int b, int c) {
    int mxA = 0, mxB = 0, mxC = 0;
    for (int i = 0; i < 720; i++) {
        if (!poss[i]) continue;
        int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
        int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
        int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
        if (idA < idB && idA < idC) mxA++;
        if (idB < idA && idB < idC) mxB++;
        if (idC < idB && idC < idA) mxC++;
    }
    return max({mxA, mxB, mxC});
}

int maxPossAfterMid(vector<bool> &poss, int a, int b, int c) {
    int mxA = 0, mxB = 0, mxC = 0;
    for (int i = 0; i < 720; i++) {
        if (!poss[i]) continue;
        int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
        int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
        int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
        if ((idA < idB) != (idA < idC)) mxA++;
        if ((idB < idA) != (idB < idC)) mxB++;
        if ((idC < idB) != (idC < idA)) mxC++;
    }
    return max({mxA, mxB, mxC});
}

int maxPossAfterHigh(vector<bool> &poss, int a, int b, int c) {
    int mxA = 0, mxB = 0, mxC = 0;
    for (int i = 0; i < 720; i++) {
        if (!poss[i]) continue;
        int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
        int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
        int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
        if (idA > idB && idA > idC) mxA++;
        if (idB > idA && idB > idC) mxB++;
        if (idC > idB && idC > idA) mxC++;
    }
    return max({mxA, mxB, mxC});
}

int maxPossAfterD(vector<bool> &poss, int a, int b, int c, int d) {
    int mxA = 0, mxB = 0, mxC = 0;
    for (int i = 0; i < 720; i++) {
        if (!poss[i]) continue;
        int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
        int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
        int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
        int idD = find(perms[i].begin(), perms[i].end(), d) - perms[i].begin();
        if (idD > idA && idD > idB && idD > idC) {
            if (idA < idB && idA < idC) mxA++;
            if (idB < idA && idB < idC) mxB++;
            if (idC < idB && idC < idA) mxC++;
            continue;
        }
        vector<ll> larger;
        if (idA > idD) larger.push_back(idA);
        if (idB > idD) larger.push_back(idB);
        if (idC > idD) larger.push_back(idC);
        ll mn = 6;
        for (auto &e : larger) {
            mn = min(mn, e);
        }
        if (mn == idA) mxA++;
        if (mn == idB) mxB++;
        if (mn == idC) mxC++;
    }
    return max({mxA, mxB, mxC});
}

void queryLow(vector<bool> &poss, ll &possCnt, int a, int b, int c) {
    int t = getLightest(a, b, c);
    for (int i = 0; i < 720; i++) {
        if (!poss[i]) continue;
        int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
        int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
        int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
        int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
        if (idT > idA || idT > idB || idT > idC) { poss[i] = false; possCnt--; }
    }
}

void queryMid(vector<bool> &poss, ll &possCnt, int a, int b, int c) {
    int t = getMedian(a, b, c);
    for (int i = 0; i < 720; i++) {
        if (!poss[i]) continue;
        int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
        int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
        int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
        int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
        if (idT <= idA && idT <= idB && idT <= idC) { poss[i] = false; possCnt--; }
        else if (idT >= idA && idT >= idB && idT >= idC) { poss[i] = false; possCnt--; }
    }
}

void queryHigh(vector<bool> &poss, ll &possCnt, int a, int b, int c) {
    int t = getHeaviest(a, b, c);
    for (int i = 0; i < 720; i++) {
        if (!poss[i]) continue;
        int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
        int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
        int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
        int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
        if (idT < idA || idT < idB || idT < idC) { poss[i] = false; possCnt--; }
    }
}

void queryD(vector<bool> &poss, ll &possCnt, int a, int b, int c, int d) {
    int t = getNextLightest(a, b, c, d);
    for (int i = 0; i < 720; i++) {
        if (!poss[i]) continue;
        int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
        int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
        int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
        int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
        int idD = find(perms[i].begin(), perms[i].end(), d) - perms[i].begin();
        if (idD > idA && idD > idB && idD > idC) {
            if (idT > idA || idT > idB || idT > idC) { poss[i] = false; possCnt--; }
            continue;
        }
        vector<ll> larger;
        if (idA > idD) larger.push_back(idA);
        if (idB > idD) larger.push_back(idB);
        if (idC > idD) larger.push_back(idC);
        ll mn = 6;
        for (auto &e : larger) {
            mn = min(mn, e);
        }
        if (mn != idT) { poss[i] = false; possCnt--; };
    }
}

void query(vector<bool> &poss, ll &possCnt) {
    mt19937 mt(time(0));
    int mnCnt = 720;
    int mnSetting = 0;
    int mnA = 1, mnB = 2, mnC = 3, resD = 4;
    for (int a = 1; a <= 6; a++) {
        for (int b = a+1; b <= 6; b++) {
            for (int c = b+1; c <= 6; c++) {
                int low = maxPossAfterLow(poss, a, b, c);
                int mid = maxPossAfterMid(poss, a, b, c);
                int high = maxPossAfterHigh(poss, a, b, c);

                int mnD = 720;
                int res1D = 0;
                for (int d = 1; d <= 6; d++) {
                    if (d == a || d == b ||d == c) continue;
                    ll r = maxPossAfterD(poss, a, b, c, d);
                    if (r < mnD) {
                        mnD = r;
                        res1D = d;
                    }
                }

                if ((mt()&1) ? low < mnCnt : low <= mnCnt) {
                    mnCnt = low;
                    mnSetting = 0;
                    mnA = a; mnB = b; mnC = c;
                }
                if ((mt()&1) ? mid < mnCnt : mid <= mnCnt) {
                    mnCnt = mid;
                    mnSetting = 1;
                    mnA = a; mnB = b; mnC = c;
                }
                if ((mt()&1) ? high < mnCnt : high <= mnCnt) {
                    mnCnt = high;
                    mnSetting = 2;
                    mnA = a; mnB = b; mnC = c;
                }
                if ((mt()&1) ? mnD < mnCnt : mnD <= mnCnt) {
                    mnCnt = mnD;
                    mnSetting = 3;
                    mnA = a; mnB = b; mnC = c; resD = res1D;
                }
            }
        }
    }
    
    if (mnSetting == 0) queryLow(poss, possCnt, mnA, mnB, mnC);
    if (mnSetting == 1) queryMid(poss, possCnt, mnA, mnB, mnC);
    if (mnSetting == 2) queryHigh(poss, possCnt, mnA, mnB, mnC);
    if (mnSetting == 3) queryD(poss, possCnt, mnA, mnB, mnC, resD);
}

void orderCoins() {
    vector<bool> poss(720, true);
    ll possCnt = 720;
    while (possCnt > 1) {
        query(poss, possCnt);
    }

    for (int i = 0; i < 720; i++) {
        if (!poss[i]) continue;
        int* W = &(perms[i][0]);
        answer(W);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In function 'void init(int)':
scales.cpp:9:15: warning: unused parameter 'T' [-Wunused-parameter]
    9 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'int maxPossAfterLow(std::vector<bool>&, int, int, int)':
scales.cpp:24:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   24 |         int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:25:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   25 |         int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:26:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   26 |         int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'int maxPossAfterMid(std::vector<bool>&, int, int, int)':
scales.cpp:38:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   38 |         int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:39:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   39 |         int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:40:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   40 |         int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'int maxPossAfterHigh(std::vector<bool>&, int, int, int)':
scales.cpp:52:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   52 |         int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:53:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   53 |         int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:54:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   54 |         int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'int maxPossAfterD(std::vector<bool>&, int, int, int, int)':
scales.cpp:66:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   66 |         int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:67:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   67 |         int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:68:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   68 |         int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:69:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   69 |         int idD = find(perms[i].begin(), perms[i].end(), d) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void queryLow(std::vector<bool>&, ll&, int, int, int)':
scales.cpp:95:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   95 |         int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:96:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   96 |         int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:97:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   97 |         int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:98:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   98 |         int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void queryMid(std::vector<bool>&, ll&, int, int, int)':
scales.cpp:107:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  107 |         int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:108:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  108 |         int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:109:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  109 |         int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:110:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  110 |         int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void queryHigh(std::vector<bool>&, ll&, int, int, int)':
scales.cpp:120:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  120 |         int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:121:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  121 |         int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:122:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  122 |         int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:123:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  123 |         int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void queryD(std::vector<bool>&, ll&, int, int, int, int)':
scales.cpp:132:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  132 |         int idT = find(perms[i].begin(), perms[i].end(), t) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:133:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  133 |         int idA = find(perms[i].begin(), perms[i].end(), a) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:134:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  134 |         int idB = find(perms[i].begin(), perms[i].end(), b) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:135:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  135 |         int idC = find(perms[i].begin(), perms[i].end(), c) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp:136:61: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  136 |         int idD = find(perms[i].begin(), perms[i].end(), d) - perms[i].begin();
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void query(std::vector<bool>&, ll&)':
scales.cpp:171:31: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  171 |                         mnD = r;
      |                               ^

• Subtask 1: 71.428571 / 100