# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
669212 |
2022-12-06T03:31:57 Z |
alvingogo |
Scales (IOI15_scales) |
C++14 |
|
117 ms |
624 KB |
#include <bits/stdc++.h>
#include "scales.h"
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
int dfs(vector<int>& x,int s);
map<vector<int>,array<int,4> > mp;
int po[7]={1,3,9,27,81,243,729};
vector<vector<int> > z;
int get(vector<int> g,int a,int b,int c,int t){
if(t==-1){
for(int i=0;i<6;i++){
if(g[i]==a || g[i]==b || g[i]==c){
return g[i];
}
}
}
else if(t==-2){
for(int i=5;i>=0;i--){
if(g[i]==a || g[i]==b || g[i]==c){
return g[i];
}
}
}
else if(t==-3){
int cnt=0;
for(int i=0;i<6;i++){
if(g[i]==a || g[i]==b || g[i]==c){
cnt++;
}
if(cnt==2){
return g[i];
}
}
}
else{
int cnt=0;
for(int i=0;i<6;i++){
if(g[i]==t){
cnt++;
}
if(cnt && (g[i]==a || g[i]==b || g[i]==c)){
return g[i];
}
}
return get(g,a,b,c,-1);
}
}
int fg(int a,int b,int c){
return getHeaviest(a+1,b+1,c+1)-1;
}
int fm(int a,int b,int c){
return getMedian(a+1,b+1,c+1)-1;
}
int fl(int a,int b,int c){
return getLightest(a+1,b+1,c+1)-1;
}
int nx(int a,int b,int c,int d){
return getNextLightest(a+1,b+1,c+1,d+1)-1;
}
inline int cal(vector<int>& x,int t,int i,int j,int k,int s){
vector<int> b,c,d;
for(auto y:x){
auto h=z[y];
int a=get(h,i,j,k,t);
if(a==i){
b.push_back(y);
}
else if(a==j){
c.push_back(y);
}
else{
d.push_back(y);
}
}
if(b.size()>po[s-1] || c.size()>po[s-1] || d.size()>po[s-1]){
return 0;
}
if(dfs(b,s-1) && dfs(c,s-1) && dfs(d,s-1)){
return 1;
}
return 0;
}
int dfs(vector<int>& x,int s){
if(s<0 || x.size()>po[s]){
return 0;
}
else if(mp.find(x)!=mp.end()){
if(mp[x][0]==-1){
return 0;
}
else{
return 1;
}
}
else if(s==0){
return 1;
}
for(int i=0;i<4;i++){
for(int j=i+1;j<5;j++){
for(int k=j+1;k<6;k++){
for(int t=-3;t<6;t++){
if(t!=i && t!=j && t!=k){
if(cal(x,t,i,j,k,s)){
mp[x]={i,j,k,t};
return 1;
}
}
}
}
}
}
mp[x]={-1,-1,-1,-1};
return 0;
}
void init(int T){
vector<int> g(6);
iota(g.begin(),g.end(),0);
for(int i=0;i<720;i++){
z.push_back(g);
next_permutation(g.begin(),g.end());
}
vector<int> k(720);
iota(k.begin(),k.end(),0);
dfs(k,6);
}
void orderCoins(){
vector<int> g(720);
iota(g.begin(),g.end(),0);
while(g.size()>1){
auto h=mp[g];
vector<int> nw;
int y;
if(h[3]==-1){
y=fl(h[0],h[1],h[2]);
}
else if(h[3]==-3){
y=fm(h[0],h[1],h[2]);
}
else if(h[3]==-2){
y=fg(h[0],h[1],h[2]);
}
else{
y=nx(h[0],h[1],h[2],h[3]);
}
for(auto r:g){
if(get(z[r],h[0],h[1],h[2],h[3])==y){
nw.push_back(r);
}
}
g=nw;
}
int ans[6];
for(int i=0;i<6;i++){
ans[i]=z[g[0]][i]+1;
}
answer(ans);
}
Compilation message
scales.cpp: In function 'int cal(std::vector<int>&, int, int, int, int, int)':
scales.cpp:80:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | if(b.size()>po[s-1] || c.size()>po[s-1] || d.size()>po[s-1]){
| ~~~~~~~~^~~~~~~~
scales.cpp:80:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | if(b.size()>po[s-1] || c.size()>po[s-1] || d.size()>po[s-1]){
| ~~~~~~~~^~~~~~~~
scales.cpp:80:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | if(b.size()>po[s-1] || c.size()>po[s-1] || d.size()>po[s-1]){
| ~~~~~~~~^~~~~~~~
scales.cpp: In function 'int dfs(std::vector<int>&, int)':
scales.cpp:89:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
89 | if(s<0 || x.size()>po[s]){
| ~~~~~~~~^~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:120:15: warning: unused parameter 'T' [-Wunused-parameter]
120 | void init(int T){
| ~~~~^
scales.cpp: In function 'int get(std::vector<int>, int, int, int, int)':
scales.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
52 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
102 ms |
536 KB |
Output is correct |
2 |
Correct |
104 ms |
484 KB |
Output is correct |
3 |
Correct |
104 ms |
548 KB |
Output is correct |
4 |
Correct |
94 ms |
588 KB |
Output is correct |
5 |
Correct |
96 ms |
524 KB |
Output is correct |
6 |
Correct |
95 ms |
504 KB |
Output is correct |
7 |
Correct |
117 ms |
504 KB |
Output is correct |
8 |
Correct |
95 ms |
540 KB |
Output is correct |
9 |
Correct |
94 ms |
460 KB |
Output is correct |
10 |
Correct |
97 ms |
560 KB |
Output is correct |
11 |
Correct |
95 ms |
552 KB |
Output is correct |
12 |
Correct |
100 ms |
460 KB |
Output is correct |
13 |
Correct |
94 ms |
536 KB |
Output is correct |
14 |
Correct |
96 ms |
548 KB |
Output is correct |
15 |
Correct |
106 ms |
592 KB |
Output is correct |
16 |
Correct |
96 ms |
544 KB |
Output is correct |
17 |
Correct |
94 ms |
480 KB |
Output is correct |
18 |
Correct |
97 ms |
588 KB |
Output is correct |
19 |
Correct |
100 ms |
540 KB |
Output is correct |
20 |
Correct |
95 ms |
560 KB |
Output is correct |
21 |
Correct |
96 ms |
504 KB |
Output is correct |
22 |
Correct |
107 ms |
588 KB |
Output is correct |
23 |
Correct |
97 ms |
580 KB |
Output is correct |
24 |
Correct |
110 ms |
480 KB |
Output is correct |
25 |
Correct |
94 ms |
536 KB |
Output is correct |
26 |
Correct |
94 ms |
500 KB |
Output is correct |
27 |
Correct |
94 ms |
460 KB |
Output is correct |
28 |
Correct |
102 ms |
624 KB |
Output is correct |
29 |
Correct |
114 ms |
516 KB |
Output is correct |
30 |
Correct |
116 ms |
564 KB |
Output is correct |
31 |
Correct |
96 ms |
552 KB |
Output is correct |
32 |
Correct |
96 ms |
532 KB |
Output is correct |
33 |
Correct |
109 ms |
616 KB |
Output is correct |
34 |
Correct |
100 ms |
568 KB |
Output is correct |
35 |
Correct |
95 ms |
548 KB |
Output is correct |
36 |
Correct |
100 ms |
520 KB |
Output is correct |
37 |
Correct |
96 ms |
516 KB |
Output is correct |
38 |
Correct |
99 ms |
560 KB |
Output is correct |
39 |
Correct |
98 ms |
588 KB |
Output is correct |
40 |
Correct |
102 ms |
492 KB |
Output is correct |