제출 #982147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982147		XCAC197	저울 (IOI15_scales)	C++14	100 / 100	871 ms	2172 KiB

scales

#include "scales.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

vector <vector<int>> pos;

vector <vector <int>> q;


void query(int atr){
    int ans = 0;
    if(q[atr][4] == 3){
        ans = getNextLightest(q[atr][0], q[atr][1], q[atr][2], q[atr][3]); 
    }else{
        if(q[atr][4] == 0){
            ans = getLightest(q[atr][0], q[atr][1], q[atr][2]);
        }else if(q[atr][4] == 1){
            ans = getMedian(q[atr][0], q[atr][1], q[atr][2]);
        }else{
            ans = getHeaviest(q[atr][0], q[atr][1], q[atr][2]);
        }
    }
  //  cout << ans << endl;
    int res = -1;
    for(int i = 0; i < 3; i++){
        if(ans == q[atr][i]){
            res = i;
        }
    }
   /* cout << atr << " " << res << endl;
    for(int i = 0; i < 5; i++){
        cout << q[atr][i] << " ";
    }
    cout << endl;*/
    vector <vector<int>> newPos;
    for(int i = 0; i < pos.size(); i++){
        if(pos[i][atr] == res){
            newPos.push_back(pos[i]);
        }
    }
    pos = newPos;

}

void init(int T) {
    for(int i = 0; i < 6; i++){
        for(int j = i+1; j < 6; j++){
            for(int k = j+1; k < 6; k++){
                q.push_back({i+1, j+1, k+1, 0, 0});
                q.push_back({i+1, j+1, k+1, 0, 1});
                q.push_back({i+1, j+1, k+1, 0, 2});
                for(int l = 0; l < 6; l++){
                    if((l != i) && (l != j) && (l != k)){
                        q.push_back({i+1, j+1, k+1, l+1, 3});
                    }
                }
            }
        }
    }
}

int atLeast(int x){
    int bestFeasable = 0;
    int cur = 1;
    while(cur < x){
        bestFeasable++;
        cur *= 3;
    }
    return bestFeasable;
}

pair <int,int> dfs(vector <vector <int>> v){
    if(v.size() <= 1){
        return make_pair(0, 0);
    }else{
        vector <pair<int, int>> ent;
        for(int i = 0; i < 120; i++){
            int cnt [3] = {0, 0, 0};
            for(int j = 0; j < v.size(); j++){
                cnt[v[j][i]]++;
            }
            int biggest = 0;
            for(int j = 0; j < 3; j++){
                biggest = max(biggest, cnt[j]);
            }
            ent.push_back(make_pair(biggest, i));
        }
        sort(ent.begin(), ent.end());
        int best = 999;
        int bestInd = 0;
        for(int ind = 0; ind < 120; ind++){
            if((atLeast(ent[ind].first)+1) < best){
                int i = ent[ind].second;
                vector <vector<int>> cat [3];
                for(int j = 0; j < v.size(); j++){
                    cat[v[j][i]].push_back(v[j]);
                }
                int mxSiz = 0;
                for(int j = 0; j < 3; j++){
                    mxSiz = max(mxSiz, (int)(cat[j].size()));
                }
                if(mxSiz != v.size()){
                    int mx = 0;
                    for(int j = 0; j < 3; j++){
                        mx = max(mx, dfs(cat[j]).first);
                    }
                    if((mx+1) < best){
                        bestInd = i;
                        best = mx+1;
                    }
                    if(best == atLeast(v.size())){
                        break;
                    }
                }
            }else{
                break;
            }
        }
        return make_pair(best, bestInd);
    }
}    

void orderCoins() {
    pos.clear();
    vector <int> perm = {1, 2, 3, 4, 5, 6};
    do{
        vector <int> v;
        for(int i = 0; i < 6; i++){
            for(int j = i+1; j < 6; j++){
                for(int k = j+1; k < 6; k++){
                    vector <pair<int,int>> abc;
                    abc.push_back(make_pair(perm[i], 0));
                    abc.push_back(make_pair(perm[j], 1));
                    abc.push_back(make_pair(perm[k], 2));
                    sort(abc.begin(), abc.end());
                    v.push_back(abc[0].second);
                    v.push_back(abc[1].second);
                    v.push_back(abc[2].second);
                    for(int l = 0; l < 6; l++){
                        if((l != i) && (l != j) && (l != k)){
                            for(int o = 0; o < 4; o++){
                                if((o == 3) || (perm[l] < abc[o].first)){
                                    v.push_back(abc[o%3].second);
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
        /*for(int i = 0; i < 6; i++){
            cout << perm[i] << " ";
        }
        cout << endl;
        for(int i = 0; i < 120; i++){
            cout << v[i] << " ";
        }
        cout << endl;*/
        pos.push_back(v);
    }while(next_permutation(perm.begin(), perm.end()));
   // cout << "BING CHILLING" << endl;
    while(pos.size() != 1){
        pair<int,int> p = dfs(pos);
        query(p.second);
    }
 //   cout << "BING CHILLING" << endl;
    
    perm = {1, 2, 3, 4, 5, 6};
    do{
        vector <int> v;
        for(int i = 0; i < 6; i++){
            for(int j = i+1; j < 6; j++){
                for(int k = j+1; k < 6; k++){
                    vector <pair<int,int>> abc;
                    abc.push_back(make_pair(perm[i], 0));
                    abc.push_back(make_pair(perm[j], 1));
                    abc.push_back(make_pair(perm[k], 2));
                    sort(abc.begin(), abc.end());
                    v.push_back(abc[0].second);
                    v.push_back(abc[1].second);
                    v.push_back(abc[2].second);
                    for(int l = 0; l < 6; l++){
                        if((l != i) && (l != j) && (l != k)){
                            for(int o = 0; o < 4; o++){
                                if((o == 3) || (perm[l] < abc[o].first)){
                                    v.push_back(abc[o%3].second);
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
        bool same = true;
        for(int i = 0; i < 120; i++){
            if(v[i] != pos[0][i]){
                same = false;
            }
        }
        if(same){
            int arr [6];
            for(int i = 0; i < perm.size(); i++){
                arr[perm[i]-1] = i+1;
            }
  //  cout << "BING CHILLING" << endl;
            answer(arr);
            return;
        }
    }while(next_permutation(perm.begin(), perm.end()));
}

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

scales.cpp: In function 'void query(int)':
scales.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0; i < pos.size(); i++){
      |                    ~~^~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:50:15: warning: unused parameter 'T' [-Wunused-parameter]
   50 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'std::pair<int, int> dfs(std::vector<std::vector<int> >)':
scales.cpp:84:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             for(int j = 0; j < v.size(); j++){
      |                            ~~^~~~~~~~~~
scales.cpp:100:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |                 for(int j = 0; j < v.size(); j++){
      |                                ~~^~~~~~~~~~
scales.cpp:107:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |                 if(mxSiz != v.size()){
      |                    ~~~~~~^~~~~~~~~~~
scales.cpp:116:46: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  116 |                     if(best == atLeast(v.size())){
      |                                        ~~~~~~^~
scales.cpp: In function 'void orderCoins()':
scales.cpp:209:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |             for(int i = 0; i < perm.size(); i++){
      |                            ~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100