Submission #922423

#	Time	Username	Problem	Language	Result	Execution time	Memory
922423		coding_snorlax	Scales (IOI15_scales)	C++14	72.02 / 100	217 ms	604 KiB

scales

#include<bits/stdc++.h>
#include "scales.h"
using namespace std;
vector<vector<int>> All_possible,tmp;
// List = {4,3,1,6,5,2} List[i] 代表 coin i 的重量
void init(int T){
    srand(time(0));
}
void init1(){
    All_possible.clear();
    for(int a1=1;a1<=6;a1++){
        for(int a2=1;a2<=6;a2++){
            for(int a3=1;a3<=6;a3++){
                for(int a4=1;a4<=6;a4++){
                    for(int a5=1;a5<=6;a5++){
                        for(int a6=1;a6<=6;a6++){
                            set<int> ct = {a1,a2,a3,a4,a5,a6};
                            if(ct.size()==6) All_possible.push_back({0,a1,a2,a3,a4,a5,a6});
                        }
                    }
                }
            }
        }
    }
}
int mock_A(int a,int b,int c){
    set<int> ct = {a,b,c};
    if((int)ct.size()!=3) return 10000;
    int tmp1 = 0,tmp2 = 0, tmp3 = 0;
    for(auto List:All_possible){
        if(List[a]>List[b] && List[a]>List[c]) tmp1++;
        else if (List[b]>List[a] && List[b]>List[c]) tmp2++;
        else tmp3++;
    }
    return max(tmp1,max(tmp2,tmp3));
}
int mock_B(int a,int b,int c){
    set<int> ct = {a,b,c};
    if((int)ct.size()!=3) return 10000;
    int tmp1 = 0,tmp2 = 0, tmp3 = 0;
    for(auto List:All_possible){
        //cout << List[0] << " ";
        if(List[a]<List[b] && List[a]<List[c]) tmp1++;
        else if (List[b]<List[a] && List[b]<List[c]) tmp2++;
        else tmp3++;
    }
    return max(tmp1,max(tmp2,tmp3));
}
int mock_C(int a,int b,int c){
    set<int> ct = {a,b,c};
    if((int)ct.size()!=3) return 10000;
    int tmp1 = 0,tmp2 = 0, tmp3 = 0;
    for(auto List:All_possible){
        if(max(List[b],List[c])>List[a] && List[a]>min(List[b],List[c])) tmp1++;
        else if(max(List[a],List[c])>List[b] && List[b]>min(List[a],List[c])) tmp2++;
        else tmp3++;
    }
    return max(tmp1,max(tmp2,tmp3));
}
int Check_A(int a,int b,int c, vector<int> List,int res){
    if(List[a]>List[b] && List[a]>List[c] && res==a) return 1;
    else if (List[b]>List[a] && List[b]>List[c] && res==b) return 1;
    else if (List[c]>List[a] && List[c]>List[b] && res==c) return 1;
    return 0;
}
 
int Check_B(int a,int b,int c, vector<int> List,int res){
    if(List[a]<List[b] && List[a]<List[c] && res==a) return 1;
    else if (List[b]<List[a] && List[b]<List[c] && res==b) return 1;
    else if (List[c]<List[a] && List[c]<List[b] && res==c) return 1;
    return 0;
}
 
int Check_C(int a,int b,int c, vector<int> List,int res){
    if(max(List[b],List[c])>List[a] && List[a]>min(List[b],List[c]) && res==a) return 1;
    else if(max(List[a],List[c])>List[b] && List[b]>min(List[a],List[c]) && res==b) return 1;
    else if(max(List[a],List[b])>List[c] && List[c]>min(List[a],List[b]) && res==c) return 1;
    return 0;
}
 
int mock_D(int a,int b,int c,int d){
    set<int> ct = {a,b,c,d};
    if((int)ct.size()!=4) return 10000;
    int tmp1 = 0,tmp2 = 0, tmp3 = 0;
    for(auto List:All_possible){
        if(List[d]>max(List[a],max(List[b],List[c])) || List[d]<min(List[a],min(List[b],List[c]))){
            if(List[a]<List[b] && List[a]<List[c]) tmp1++;
            else if (List[b]<List[a] && List[b]<List[c]) tmp2++;
            else tmp3++;
        }
        else if(List[a]>List[d] && List[d]>max(List[b],List[c])) tmp1++;
        else if(List[b]>List[d] && List[d]>max(List[a],List[c])) tmp2++;
        else if(List[c]>List[d] && List[d]>max(List[b],List[a])) tmp3++;
 
        else if(List[a]>max(List[b],List[c]) && List[b]>List[d]) tmp2++;
        else if(List[a]>max(List[b],List[c]) && List[c]>List[d]) tmp3++;
 
        else if(List[b]>max(List[a],List[c]) && List[a]>List[d]) tmp1++;
        else if(List[b]>max(List[a],List[c]) && List[c]>List[d]) tmp3++;
 
        else if(List[c]>max(List[b],List[a]) && List[a]>List[d]) tmp1++;
        else if(List[c]>max(List[b],List[a]) && List[b]>List[d]) tmp2++;
    }
    return max(tmp1,max(tmp2,tmp3));
}
 
int Check_D(int a,int b,int c,int d,vector<int> List,int res){
    if(List[d]>max(List[a],max(List[b],List[c])) || List[d]<min(List[a],min(List[b],List[c]))){
        if(List[a]<List[b] && List[a]<List[c] && res==a) return 1;
        else if (List[b]<List[a] && List[b]<List[c] && res==b) return 1;
        else if (List[c]<List[a] && List[c]<List[b] && res==c) return 1;
        else return 0;
    }
    else if(List[a]>List[d] && List[d]>max(List[b],List[c]) && res==a) return 1;
    else if(List[b]>List[d] && List[d]>max(List[a],List[c]) && res==b) return 1;
    else if(List[c]>List[d] && List[d]>max(List[b],List[a]) && res==c) return 1;
 
    else if(List[a]>max(List[b],List[c]) && List[b]>List[d] && res==b) return 1;
    else if(List[a]>max(List[b],List[c]) && List[c]>List[d] && res==c) return 1;
 
    else if(List[b]>max(List[a],List[c]) && List[a]>List[d] && res==a) return 1;
    else if(List[b]>max(List[a],List[c]) && List[c]>List[d] && res==c) return 1;
 
    else if(List[c]>max(List[b],List[a]) && List[a]>List[d] && res==a) return 1;
    else if(List[c]>max(List[b],List[a]) && List[b]>List[d] && res==b) return 1;
    else return 0;
}
void orderCoins(){
    init1();
    while(All_possible.size()>1){
        int Q_index,tmp1,tmp2,tmp3,tmp5,Total=720;
        for(int i=1;i<=6;i++){
            for(int j=i+1;j<=6;j++){
                for(int k=j+1;k<=6;k++){
                    int tmp4 = mock_A(i,j,k);
                    if(tmp4<Total || (tmp4==Total && rand()%2==0)){
                        Total = tmp4;tmp1 = i;tmp2 = j;tmp3 = k;Q_index=1;
                    }
                    tmp4 = mock_B(i,j,k);
                    if(tmp4<Total|| (tmp4==Total && rand()%2==0)){
                        Total = tmp4;tmp1 = i;tmp2 = j;tmp3 = k;Q_index=2;
                    }
                    tmp4 = mock_C(i,j,k);
                    if(tmp4<Total|| (tmp4==Total && rand()%2==0)){
                        Total = tmp4;tmp1 = i;tmp2 = j;tmp3 = k;Q_index=3;
                    }
                }
            }
        }
 
        for(int i=1;i<=6;i++){
            for(int j=i+1;j<=6;j++){
                for(int k=j+1;k<=6;k++){
                    for(int l=1;l<=6;l++){
                        int tmp4 = mock_D(i,j,k,l);
                        if(tmp4<Total|| (tmp4==Total && rand()%2==0)){
                            Total = tmp4;tmp1 = i;tmp2 = j;tmp3 = k;tmp5=l;Q_index=4;
                        }
                    }
                }
            }
        }
        tmp.clear();
        int res;
        if(Q_index==1){
            res = getHeaviest(tmp1,tmp2,tmp3);
            for(auto i:All_possible){
                if(Check_A(tmp1,tmp2,tmp3,i,res)) tmp.push_back(i);
            }
        }
        else if(Q_index==2){
            res = getLightest(tmp1,tmp2,tmp3);
            for(auto i:All_possible){
                if(Check_B(tmp1,tmp2,tmp3,i,res)) tmp.push_back(i);
            }
        }
        else if(Q_index==3){
            res = getMedian(tmp1,tmp2,tmp3);
            for(auto i:All_possible){
                if(Check_C(tmp1,tmp2,tmp3,i,res)) tmp.push_back(i);
            }
        }
        else if(Q_index==4){
            res = getNextLightest(tmp1,tmp2,tmp3,tmp5);
            for(auto i:All_possible){
                if(Check_D(tmp1,tmp2,tmp3,tmp5,i,res)) tmp.push_back(i);
            }
        }
        All_possible = tmp;
    }
    int Answer[6];
    for(int i=1;i<=6;i++){
        Answer[All_possible[0][i]-1]=i;
    }
    answer(Answer);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:7:15: warning: conversion from 'time_t' {aka 'long int'} to 'unsigned int' may change value [-Wconversion]
    7 |     srand(time(0));
      |           ~~~~^~~
scales.cpp:6:15: warning: unused parameter 'T' [-Wunused-parameter]
    6 | void init(int T){
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:186:27: warning: 'tmp5' may be used uninitialized in this function [-Wmaybe-uninitialized]
  186 |                 if(Check_D(tmp1,tmp2,tmp3,tmp5,i,res)) tmp.push_back(i);
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:168:27: warning: 'tmp3' may be used uninitialized in this function [-Wmaybe-uninitialized]
  168 |                 if(Check_A(tmp1,tmp2,tmp3,i,res)) tmp.push_back(i);
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
scales.cpp:168:27: warning: 'tmp2' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:168:27: warning: 'tmp1' may be used uninitialized in this function [-Wmaybe-uninitialized]
scales.cpp:183:14: warning: 'Q_index' may be used uninitialized in this function [-Wmaybe-uninitialized]
  183 |         else if(Q_index==4){
      |              ^~

• Subtask 1: 72.02381 / 100