제출 #1211523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211523		XCAC197	Scales (IOI15_scales)	C++17	73.51 / 100	10 ms	788 KiB

scales

#include "scales.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int res [720][120];
int perm [720][6];//permutations
vector <int> ops [120];//operations
int _ind[6];


int _getMedian(int A, int B, int C) {

    A--; B--; C--;

    if (_ind[B] < _ind[A] && _ind[A] < _ind[C])
        return A + 1;

    if (_ind[C] < _ind[A] && _ind[A] < _ind[B])
        return A + 1;

    if (_ind[A] < _ind[B] && _ind[B] < _ind[C])
        return B + 1;

    if (_ind[C] < _ind[B] && _ind[B] < _ind[A])
        return B + 1;

    return C + 1;
}

int _getHeaviest(int A, int B, int C) {

    A--; B--; C--;

    if (_ind[A] > _ind[B] && _ind[A] > _ind[C])
        return A + 1;

    if (_ind[B] > _ind[A] && _ind[B] > _ind[C])
        return B + 1;

    return C + 1;
}

int _getLightest(int A, int B, int C) {

    A--; B--; C--;

    if (_ind[A] < _ind[B] && _ind[A] < _ind[C])
        return A + 1;
    
    if (_ind[B] < _ind[A] && _ind[B] < _ind[C])
        return B + 1;

    return C + 1;
}

int _getNextLightest(int A, int B, int C, int D) {
    int allLess = 1;    

    A--; B--; C--; D--;

    if (_ind[A] > _ind[D] || _ind[B] > _ind[D] || _ind[C] > _ind[D])
        allLess = 0;

    if (allLess == 1) {
        if (_ind[A] < _ind[B] && _ind[A] < _ind[C])
            return A + 1;
    
        if (_ind[B] < _ind[A] && _ind[B] < _ind[C])
            return B + 1;

        return C + 1;
    }

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

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

    return C + 1;
}

//returns -1 if impossible
//else returns the operation
/*
int solve(vector <pair<int,int>> constraints, int numGuessesLeft){
    for(int i = 0; i < 120; i++){

    }
}*/

void init(int T) {
    int tri [20][3] = 
    {{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 2, 6}, {1, 3, 4}, {1, 3, 5}, {1, 3, 6}, {1, 4, 5}, {1, 4, 6}, {1, 5, 6}, 
    {2, 3, 4}, {2, 3, 5}, {2, 3, 6}, {2, 4, 5}, {2, 4, 6}, {2, 5, 6},
    {3, 4, 5}, {3, 4, 6}, {3, 5, 6},
    {4, 5, 6}};
    int tmp = 60;
    for(int i = 0; i < 20; i++){
        ops[i].push_back(1);
        ops[20+i].push_back(2);
        ops[40+i].push_back(3);
        for(int j = 0; j < 3; j++){
            ops[i].push_back(tri[i][j]);
            ops[20+i].push_back(tri[i][j]);
            ops[40+i].push_back(tri[i][j]);
        }
        for(int j = 1; j <= 6; j++){
            if(j != tri[i][0] && j != tri[i][1] && j != tri[i][2]){
                ops[tmp].push_back(4);
                for(int k = 0; k < 3; k++){
                    ops[tmp].push_back(tri[i][k]);
                }
                ops[tmp].push_back(j);
                tmp++;
            }
        }
    }

   // cerr << "BRUH" << endl;
    int W[] = {1, 2, 3, 4, 5, 6};
    int cur = 0;
    do{
        for(int i = 0; i < 6; i++){
            perm[cur][i] = W[i];
            _ind[W[i]-1] = i+1;
        }
        for(int i = 0; i < 120; i++){
            int type = ops[i][0];
            if(type == 1){
                res[cur][i] = _getMedian(ops[i][1], ops[i][2], ops[i][3]);
            }else if(type == 2){
                res[cur][i] = _getHeaviest(ops[i][1], ops[i][2], ops[i][3]);
            }else if(type == 3){
                res[cur][i] = _getLightest(ops[i][1], ops[i][2], ops[i][3]);
            }else{
                res[cur][i] = _getNextLightest(ops[i][1], ops[i][2], ops[i][3], ops[i][4]);
            }
        }
        cur++;
    }
    while(next_permutation(W, W+6));
    cerr << "ok" << endl;
}



void orderCoins() {
    //apply operations, and pick the one that reduces biggest
    vector <pair<int,int>> constraints;
  //  while(true){
    for(int i = 0; i < 30; i++){
        int num = 0;
        bool sat [720];
        int permind = 0;
        for(int i = 0; i < 720; i++){
            sat[i] = true;
            for(int j = 0; j < constraints.size(); j++){
                if(res[i][constraints[j].first] != constraints[j].second){
                    sat[i] = false;
                }
            }
            if(sat[i]){
                permind = i;
                num++;
            }
        }
     //   cerr << num << endl;
        if(num == 1){
            answer(perm[permind]);
            break;
        }
        int bestOp = 0;
        int bopScore = 720;
        for(int i = 0; i < 120; i++){
            int cnt [7] = {0, 0, 0, 0, 0, 0, 0};
            for(int j = 0; j < 720; j++){
              //  cout << res[j][i];
                if(sat[j]){
                    cnt[res[j][i]]++;
                }
            }
        //    cout << endl;
            int mop = 0;
            for(int j = 0; j <= 6; j++){
                mop = max(mop, cnt[j]);
            }
            if(bopScore > mop){
                bestOp = i;
                bopScore = mop;
            }
        }
        /*cerr << num << endl;
        cerr << bestOp << "/" << bopScore << endl;
        for(int j = 0; j < ops[bestOp].size(); j++){
            cerr << ops[bestOp][j] << " ";
        }
        cerr << endl;*/
        int bopResult = 0;
        int type = ops[bestOp][0];
        if(type == 1){
            bopResult = getMedian(ops[bestOp][1], ops[bestOp][2], ops[bestOp][3]);
        }else if(type == 2){
            bopResult = getHeaviest(ops[bestOp][1], ops[bestOp][2], ops[bestOp][3]);
        }else if(type == 3){
            bopResult = getLightest(ops[bestOp][1], ops[bestOp][2], ops[bestOp][3]);
        }else{
            bopResult = getNextLightest(ops[bestOp][1], ops[bestOp][2], ops[bestOp][3], ops[bestOp][4]);
        }
        constraints.push_back(make_pair(bestOp, bopResult));
    }
}

• Subtask 1: 73.5119 / 100