| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 678917 |
2023-01-06T23:05:10 Z |
n0sk1ll |
Scales (IOI15_scales) |
C++14 |
|
386 ms |
237024 KB |
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
#include "scales.h"
vector<vector<int>> perms;
mt19937 rng(29042004);
int evalmin(int a, int b, int c)
{
int ka=0,kb=0,kc=0;
for (auto p : perms)
{
for (auto it : p)
{
if (it==a) {ka++; break;}
if (it==b) {kb++; break;}
if (it==c) {kc++; break;}
}
}
return max(max(ka,kb),kc)-min(min(ka,kb),kc);
}
int evalmed(int a, int b, int c)
{
int ka=0,kb=0,kc=0;
for (auto p : perms)
{
int red=0;
for (auto it : p)
{
if (it==a) {if (red==1) {ka++; break;} else red++;}
if (it==b) {if (red==1) {kb++; break;} else red++;}
if (it==c) {if (red==1) {kc++; break;} else red++;}
}
}
return max(max(ka,kb),kc)-min(min(ka,kb),kc);
}
int evalmax(int a, int b, int c)
{
int ka=0,kb=0,kc=0;
for (auto p : perms)
{
int red=0;
for (auto it : p)
{
if (it==a) {if (red==2) {ka++; break;} else red++;}
if (it==b) {if (red==2) {kb++; break;} else red++;}
if (it==c) {if (red==2) {kc++; break;} else red++;}
}
}
return max(max(ka,kb),kc)-min(min(ka,kb),kc);
}
int evalwtf(int a, int b, int c, int d)
{
int ka=0,kb=0,kc=0;
for (auto p : perms)
{
int red=0; bool svrsio=0; bool oki=false;
for (auto it : p)
{
if (it==a) {if (oki) {ka++; svrsio=1; break;}}
if (it==b) {if (oki) {kb++; svrsio=1; break;}}
if (it==c) {if (oki) {kc++; svrsio=1; break;}}
if (it==d) oki=true;
}
if (!svrsio) for (auto it : p)
{
if (it==a) {ka++; break;}
if (it==b) {kb++; break;}
if (it==c) {kc++; break;}
}
}
return max(max(ka,kb),kc)-min(min(ka,kb),kc);
}
int idx=1;
int g[10000007][3];
vector<int> stapitam[10000007]; //ne pitam nista ako znam odgovor
bool generate_tree(int p, vector<vector<int>> sperms, int d)
{
//cout<<p<<" "<<sperms.size()<<" "<<d<<endl;
if (d>=7) return false;
if (sperms.size()==1)
{
stapitam[p]=sperms.back();
return true;
}
if (sperms.empty()) return true;
perms=sperms;
vector<vector<int>> qrys;
int sta=837339;
fff(i,1,6) fff(j,i+1,6) fff(k,j+1,6)
{
int tval;
fff(_,1,6) if (_!=i && _!=j && _!=k)
{
tval=evalwtf(i,j,k,_);
if (tval<sta) qrys.clear(),sta=tval;
if (tval==sta) qrys.pb({4,i,j,k,_});
}
tval=evalmed(i,j,k);
if (tval<sta) qrys.clear(),sta=tval;
if (tval==sta) qrys.pb({2,i,j,k});
tval=evalmin(i,j,k);
if (tval<sta) qrys.clear(),sta=tval;
if (tval==sta) qrys.pb({1,i,j,k});
tval=evalmax(i,j,k);
if (tval<sta) qrys.clear(),sta=tval;
if (tval==sta) qrys.pb({3,i,j,k});
}
shuffle(all(qrys),rng);
int upito=0;
for (auto qq : qrys)
{
if (upito>sperms.size()/80+5) return false;
upito++;
stapitam[p]=qq;
vector<vector<int>> gde1,gde2,gde3;
if (qq[0]==1)
{
int a=qq[1],b=qq[2],c=qq[3];
for (auto p : sperms)
{
for (auto it : p)
{
if (it==a) {gde1.pb(p); break;}
if (it==b) {gde2.pb(p); break;}
if (it==c) {gde3.pb(p); break;}
}
}
}
if (qq[0]==2)
{
int a=qq[1],b=qq[2],c=qq[3];
for (auto p : sperms)
{
int red=0;
for (auto it : p)
{
if (it==a) {if (red==1) {gde1.pb(p); break;} else red++;}
if (it==b) {if (red==1) {gde2.pb(p); break;} else red++;}
if (it==c) {if (red==1) {gde3.pb(p); break;} else red++;}
}
}
}
if (qq[0]==3)
{
int a=qq[1],b=qq[2],c=qq[3];
for (auto p : sperms)
{
int red=0;
for (auto it : p)
{
if (it==a) {if (red==2) {gde1.pb(p); break;} else red++;}
if (it==b) {if (red==2) {gde2.pb(p); break;} else red++;}
if (it==c) {if (red==2) {gde3.pb(p); break;} else red++;}
}
}
}
if (qq[0]==4)
{
int a=qq[1],b=qq[2],c=qq[3],d=qq[4];
for (auto p : sperms)
{
int red=0; bool svrsio=0; bool oki=false;
for (auto it : p)
{
if (it==a) {if (oki) {gde1.pb(p); svrsio=1; break;}}
if (it==b) {if (oki) {gde2.pb(p); svrsio=1; break;}}
if (it==c) {if (oki) {gde3.pb(p); svrsio=1; break;}}
if (it==d) oki=true;
}
if (!svrsio) for (auto it : p)
{
if (it==a) {gde1.pb(p); break;}
if (it==b) {gde2.pb(p); break;}
if (it==c) {gde3.pb(p); break;}
}
}
}
//cout<<qq[0]<<" ? "<<gde1.size()<<" "<<gde2.size()<<" "<<gde3.size()<<endl;
bool ok=true;
g[p][0]=++idx;
g[p][1]=++idx;
g[p][2]=++idx;
if (!generate_tree(g[p][0],gde1,d+1)) ok=false;
if (!generate_tree(g[p][1],gde2,d+1)) ok=false;
if (!generate_tree(g[p][2],gde3,d+1)) ok=false;
if (ok) return true;
}
return false;
}
void init(int T)
{
vector<int> tperm={1,2,3,4,5,6};
do
{
perms.pb(tperm);
} while (next_permutation(all(tperm)));
assert(generate_tree(1,perms,0));
}
int ans[6];
void dfs(int p)
{
if (stapitam[p].size()==6)
{
ff(i,0,6) ans[i]=stapitam[p][i];
answer(ans);
}
else if (stapitam[p].front()==1)
{
int x=getLightest(stapitam[p][1],stapitam[p][2],stapitam[p][3]);
if (x==stapitam[p][1]) dfs(g[p][0]);
if (x==stapitam[p][2]) dfs(g[p][1]);
if (x==stapitam[p][3]) dfs(g[p][2]);
}
else if (stapitam[p].front()==2)
{
int x=getMedian(stapitam[p][1],stapitam[p][2],stapitam[p][3]);
if (x==stapitam[p][1]) dfs(g[p][0]);
if (x==stapitam[p][2]) dfs(g[p][1]);
if (x==stapitam[p][3]) dfs(g[p][2]);
}
else if (stapitam[p].front()==3)
{
int x=getHeaviest(stapitam[p][1],stapitam[p][2],stapitam[p][3]);
if (x==stapitam[p][1]) dfs(g[p][0]);
if (x==stapitam[p][2]) dfs(g[p][1]);
if (x==stapitam[p][3]) dfs(g[p][2]);
}
else
{
int x=getNextLightest(stapitam[p][1],stapitam[p][2],stapitam[p][3],stapitam[p][4]);
if (x==stapitam[p][1]) dfs(g[p][0]);
if (x==stapitam[p][2]) dfs(g[p][1]);
if (x==stapitam[p][3]) dfs(g[p][2]);
}
}
void orderCoins()
{
dfs(1);
}
Compilation message
scales.cpp: In function 'int evalwtf(int, int, int, int)':
scales.cpp:97:13: warning: unused variable 'red' [-Wunused-variable]
97 | int red=0; bool svrsio=0; bool oki=false;
| ^~~
scales.cpp: In function 'bool generate_tree(int, std::vector<std::vector<int> >, int)':
scales.cpp:14:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
| ^
scales.cpp:134:5: note: in expansion of macro 'fff'
134 | fff(i,1,6) fff(j,i+1,6) fff(k,j+1,6)
| ^~~
scales.cpp:14:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
14 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
| ^
scales.cpp:134:16: note: in expansion of macro 'fff'
134 | fff(i,1,6) fff(j,i+1,6) fff(k,j+1,6)
| ^~~
scales.cpp:14:29: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
14 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
| ^
scales.cpp:134:29: note: in expansion of macro 'fff'
134 | fff(i,1,6) fff(j,i+1,6) fff(k,j+1,6)
| ^~~
scales.cpp:14:29: warning: unnecessary parentheses in declaration of '_' [-Wparentheses]
14 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
| ^
scales.cpp:138:9: note: in expansion of macro 'fff'
138 | fff(_,1,6) if (_!=i && _!=j && _!=k)
| ^~~
scales.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | if (upito>sperms.size()/80+5) return false;
| ~~~~~^~~~~~~~~~~~~~~~~~~
scales.cpp:172:23: warning: declaration of 'auto p' shadows a parameter [-Wshadow]
172 | for (auto p : sperms)
| ^
scales.cpp:119:24: note: shadowed declaration is here
119 | bool generate_tree(int p, vector<vector<int>> sperms, int d)
| ~~~~^
scales.cpp:185:23: warning: declaration of 'auto p' shadows a parameter [-Wshadow]
185 | for (auto p : sperms)
| ^
scales.cpp:119:24: note: shadowed declaration is here
119 | bool generate_tree(int p, vector<vector<int>> sperms, int d)
| ~~~~^
scales.cpp:199:23: warning: declaration of 'auto p' shadows a parameter [-Wshadow]
199 | for (auto p : sperms)
| ^
scales.cpp:119:24: note: shadowed declaration is here
119 | bool generate_tree(int p, vector<vector<int>> sperms, int d)
| ~~~~^
scales.cpp:212:41: warning: declaration of 'int d' shadows a parameter [-Wshadow]
212 | int a=qq[1],b=qq[2],c=qq[3],d=qq[4];
| ^
scales.cpp:119:59: note: shadowed declaration is here
119 | bool generate_tree(int p, vector<vector<int>> sperms, int d)
| ~~~~^
scales.cpp:213:23: warning: declaration of 'auto p' shadows a parameter [-Wshadow]
213 | for (auto p : sperms)
| ^
scales.cpp:119:24: note: shadowed declaration is here
119 | bool generate_tree(int p, vector<vector<int>> sperms, int d)
| ~~~~^
scales.cpp:215:21: warning: unused variable 'red' [-Wunused-variable]
215 | int red=0; bool svrsio=0; bool oki=false;
| ^~~
scales.cpp: In function 'void init(int)':
scales.cpp:247:15: warning: unused parameter 'T' [-Wunused-parameter]
247 | void init(int T)
| ~~~~^
scales.cpp: In function 'void dfs(int)':
scales.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
13 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
| ^
scales.cpp:263:9: note: in expansion of macro 'ff'
263 | ff(i,0,6) ans[i]=stapitam[p][i];
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
299 ms |
237024 KB |
Output is correct |
| 2 |
Correct |
294 ms |
236944 KB |
Output is correct |
| 3 |
Correct |
301 ms |
236976 KB |
Output is correct |
| 4 |
Correct |
314 ms |
236848 KB |
Output is correct |
| 5 |
Correct |
297 ms |
236956 KB |
Output is correct |
| 6 |
Correct |
318 ms |
236956 KB |
Output is correct |
| 7 |
Correct |
298 ms |
236928 KB |
Output is correct |
| 8 |
Correct |
301 ms |
236888 KB |
Output is correct |
| 9 |
Correct |
297 ms |
236956 KB |
Output is correct |
| 10 |
Correct |
312 ms |
236964 KB |
Output is correct |
| 11 |
Correct |
299 ms |
236960 KB |
Output is correct |
| 12 |
Correct |
309 ms |
236912 KB |
Output is correct |
| 13 |
Correct |
298 ms |
236868 KB |
Output is correct |
| 14 |
Correct |
297 ms |
237008 KB |
Output is correct |
| 15 |
Correct |
300 ms |
236908 KB |
Output is correct |
| 16 |
Correct |
292 ms |
236864 KB |
Output is correct |
| 17 |
Correct |
323 ms |
236876 KB |
Output is correct |
| 18 |
Correct |
295 ms |
236908 KB |
Output is correct |
| 19 |
Correct |
305 ms |
236944 KB |
Output is correct |
| 20 |
Correct |
304 ms |
236840 KB |
Output is correct |
| 21 |
Correct |
365 ms |
236896 KB |
Output is correct |
| 22 |
Correct |
305 ms |
236864 KB |
Output is correct |
| 23 |
Correct |
341 ms |
236860 KB |
Output is correct |
| 24 |
Correct |
348 ms |
236860 KB |
Output is correct |
| 25 |
Correct |
311 ms |
236908 KB |
Output is correct |
| 26 |
Correct |
306 ms |
236908 KB |
Output is correct |
| 27 |
Correct |
357 ms |
236892 KB |
Output is correct |
| 28 |
Correct |
343 ms |
236904 KB |
Output is correct |
| 29 |
Correct |
372 ms |
236852 KB |
Output is correct |
| 30 |
Correct |
354 ms |
236960 KB |
Output is correct |
| 31 |
Correct |
386 ms |
236840 KB |
Output is correct |
| 32 |
Correct |
339 ms |
236940 KB |
Output is correct |
| 33 |
Correct |
330 ms |
236928 KB |
Output is correct |
| 34 |
Correct |
344 ms |
236956 KB |
Output is correct |
| 35 |
Correct |
335 ms |
236852 KB |
Output is correct |
| 36 |
Correct |
339 ms |
236852 KB |
Output is correct |
| 37 |
Correct |
335 ms |
236880 KB |
Output is correct |
| 38 |
Correct |
322 ms |
236932 KB |
Output is correct |
| 39 |
Correct |
320 ms |
236944 KB |
Output is correct |
| 40 |
Correct |
347 ms |
236964 KB |
Output is correct |
