Submission #922426

#TimeUsernameProblemLanguageResultExecution timeMemory
922426coding_snorlaxScales (IOI15_scales)C++14
71.43 / 100
215 ms592 KiB
#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){
      |              ^~
#Verdict Execution timeMemoryGrader output
Fetching results...