Submission #1242324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242324		KindaGoodGames	Scales (IOI15_scales)	C++20	33.33 / 100	0 ms	328 KiB

scales

#include "scales.h"
#include<bits/stdc++.h>

using namespace std;

void init(int T) {
    /* ... */
}

void orderCoins() {
    // 3 queries
    int lo1 = getLightest(1,2,3);
    int lo2 = getLightest(4,5,6);
    int lo = -1;
    if(lo1 != 5 && lo2 != 5){
        lo = getLightest(lo1,5,lo2); 
    }else if(lo1 != 4 && lo2 != 4){
        lo = getLightest(lo1,4,lo2); 
    }else{
        lo = getLightest(lo1,3,lo2);  
    }

    int pt = 1;
    int ans[] = {lo,-1,-1,-1,-1,-1};

    set<int> left;
    for(int i = 1; i <= 6; i++){
        left.insert(i);
    }
    left.erase(lo);
    for(int k = 0; k < 3; k++){

        vector<int> notLo;
        for(int t = 0; t < 4; t++){ 
            for(int i = 1; i <= 6; i++){
                if(i == lo || !left.count(i)) continue;
                notLo.push_back(i);
            } 
        }
        int nlo = -1;

        // 2 x 2 queries
        if(k <= 1){ 
            vector<int> q1;
            vector<int> q2;

            int ind = 0;
            while(q1.size() < 3){
                if(find(q1.begin(),q1.end(), notLo[ind]) == q1.end()){
                    q1.push_back(notLo[ind]);
                }
                ind++;
            }
            while(q2.size() < 3){
                if(find(q2.begin(),q2.end(), notLo[ind]) == q2.end()){
                    q2.push_back(notLo[ind]);
                }
                ind++;
            }

            int nlo1 = -1;
            if(q1[0] == 1 && q1[1] == 2 && q1[2] == 3){
                nlo1 = lo1;
            }else if(q1[0] == 4 && q1[1] == 5 && q1[2] == 6){
                nlo1 = lo2; 
            }else{ 
                nlo1 = getNextLightest(q1[0],q1[1],q1[2],lo);  
            }


            int nlo2 = -1;
            if(q2[0] == 1 && q2[1] == 2 && q2[2] == 3){
                nlo2 = lo1;
            }
            else if(q2[0] == 4 && q2[1] == 5 && q2[2] == 6){ 
                nlo2 = lo2;
            }else{ 
                nlo2 = getNextLightest(q2[0],q2[1],q2[2],lo);  
            } 
            if(nlo1 == nlo2){
                nlo = nlo1;
            }else{
                // eventually 2x1 query
                nlo = getMedian(lo,nlo1,nlo2);
            }
        }
        // 1 x 1 queries
        else{
            vector<int> q;
            for(int i = 0; i < 6; i++){
                if(left.count(i+1)){
                    q.push_back(i+1);
                }
            }
            nlo = getLightest(q[0],q[1],q[2]);
        }

        lo = nlo;
        ans[pt++] = lo;
        left.erase(lo);
    }
    // 1 x 1 queries
    int f = getMedian(ans[0], *left.begin(), *left.rbegin());
    ans[4] = f;
    left.erase(f);
    ans[5] = *left.begin();

    answer(ans);
}

• Subtask 1: 33.3333 / 100