| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 945248 |
2024-03-13T15:03:46 Z |
Lobo |
Scales (IOI15_scales) |
C++17 |
|
83 ms |
1148 KB |
#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = -1;
vector<vector<int>> allp, queries;
void init(int T) {
vector<int> p = {0,1,2,3,4,5,6};
while(p[0] == 0) {
allp.pb(p);
next_permutation(all(p));
}
for(int a = 1; a <= 6; a++) {
for(int b = a+1; b <= 6; b++) {
for(int c = b+1; c <= 6; c++) {
queries.pb(vector<int>{0,a,b,c});
queries.pb(vector<int>{1,a,b,c});
queries.pb(vector<int>{2,a,b,c});
for(int d = 1; d <= 6; d++) {
if(d == a or d == b or d == c) continue;
queries.pb(vector<int>{3,a,b,c,d});
}
}
}
}
/* ... */
}
// 0 L
// 1 M
// 2 H
// 3 S
// ABC(3->D)
// resp
vector<vector<int>> postot(vector<vector<int>> &disp, vector<int> &vec) {
vector<vector<int>> ansp;
for(auto p : disp) {
bool ok = true;
int tp = vec[0];
int res = vec.back();
if(tp == 0) {
int a = vec[1];
int b = vec[2];
int c = vec[3];
if(min({p[a],p[b],p[c]}) != p[res]) {
ok = false;
}
}
else if(tp == 1) {
int a = vec[1];
int b = vec[2];
int c = vec[3];
if(p[a]+p[b]+p[c] - min({p[a],p[b],p[c]}) - max({p[a],p[b],p[c]}) != p[res]) {
ok = false;
}
}
else if(tp == 2) {
int a = vec[1];
int b = vec[2];
int c = vec[3];
if(max({p[a],p[b],p[c]}) != p[res]) {
ok = false;
}
}
else if(tp == 3) {
int a = vec[1];
int b = vec[2];
int c = vec[3];
int d = vec[4];
if(p[d] > max({p[a],p[b],p[c]})) {
if(p[res] != min({p[a],p[b],p[c]})) {
ok = false;
}
}
else {
int anshere = 7;
if(p[a] > p[d]) anshere = min(anshere,p[a]);
if(p[b] > p[d]) anshere = min(anshere,p[b]);
if(p[c] > p[d]) anshere = min(anshere,p[c]);
if(anshere != p[res]) {
ok = false;
}
}
}
if(ok) {
ansp.pb(p);
}
}
return ansp;
}
map<vector<vector<int>>,int> dp;
int sol(vector<vector<int>> ps) {
if(dp.count(ps)) return dp[ps];
if(ps.size() == 0) return dp[ps] = 0;
if(ps.size() == 1) return dp[ps] = 0;
vector<vector<int>> mns;
for(auto qr : queries) {
auto qr1 = qr;
qr1.pb(0);
int mx = 0;
qr1.back() = qr[1];
mx = max(mx,(int) postot(ps,qr1).size());
qr1.back() = qr[2];
mx = max(mx,(int) postot(ps,qr1).size());
qr1.back() = qr[3];
mx = max(mx,(int) postot(ps,qr1).size());
if(mx == ((int) ps.size()+2)/3) {
mns.pb(qr);
}
}
dp[ps] = 8;
// random_shuffle(all(mns));
for(auto qr : mns) {
auto qr1 = qr;
qr1.pb(0);
qr1.back() = qr[1];
auto p1 = postot(ps,qr1);
qr1.back() = qr[2];
auto p2 = postot(ps,qr1);
qr1.back() = qr[3];
auto p3 = postot(ps,qr1);
int mx = max({sol(p1),sol(p2),sol(p3)})+1;
dp[ps] = min(dp[ps],mx);
if(ps.size() > 1 && mx == 1) break;
if(ps.size() > 3 && mx == 2) break;
if(ps.size() > 9 && mx == 3) break;
if(ps.size() > 27 && mx == 4) break;
}
return dp[ps];
}
void orderCoins() {
srand(chrono::system_clock::now().time_since_epoch().count());
vector<vector<int>> perms = allp;
int resp1;
while(true) {
vector<int> qrnew;
if(perms.size() == 720) {
qrnew = {1,1,2,3};
}
else if(perms.size() == 240) {
qrnew = {3,4,5,6,(resp1 == 1 ? 2 : 1)};
}
else {
// cout << perms.size() << " " << sol(perms) << endl;
vector<vector<int>> mns;
for(auto qr : queries) {
auto qr1 = qr;
qr1.pb(0);
int mx = 0;
qr1.back() = qr[1];
auto p1 = postot(perms,qr1);
qr1.back() = qr[2];
auto p2 = postot(perms,qr1);
qr1.back() = qr[3];
auto p3 = postot(perms,qr1);
mx = max({p1.size(),p2.size(),p3.size()});
if(mx == ((int) perms.size()+2)/3) {
mns.pb(qr);
}
}
// cout << mns.size() << endl;
// random_shuffle(all(mns));
for(auto qr : mns) {
auto qr1 = qr;
qr1.pb(0);
qr1.back() = qr[1];
auto p1 = postot(perms,qr1);
qr1.back() = qr[2];
auto p2 = postot(perms,qr1);
qr1.back() = qr[3];
auto p3 = postot(perms,qr1);
int mx = max({sol(p1),sol(p2),sol(p3)})+1;
qrnew = qr;
if(perms.size() > 1 && mx == 1) break;
if(perms.size() > 3 && mx == 2) break;
if(perms.size() > 9 && mx == 3) break;
if(perms.size() > 27 && mx == 4) break;
}
}
auto qr = qrnew;
if(qr[0] == 0) {
qr.pb(getLightest(qr[1],qr[2],qr[3]));
}
if(qr[0] == 1) {
qr.pb(getMedian(qr[1],qr[2],qr[3]));
}
if(qr[0] == 2) {
qr.pb(getHeaviest(qr[1],qr[2],qr[3]));
}
if(qr[0] == 3) {
qr.pb(getNextLightest(qr[1],qr[2],qr[3],qr[4]));
}
if(perms.size() == 720) {
resp1 = qr.back();
}
// cout << " " << perms.size() << endl;
// for(auto x : qr) cout << x << endl;
// cout << endl;
// cout << mnqr.fr << endl;
// cout << " " << postot(perms,qrsofar).size() << endl;
// auto p = postot(perms,qrsofar)[0];
// for(int i = 1; i <= 6; i++) cout << p[i] << " "; cout << endl;
// p = postot(perms,qrsofar)[1];
// for(int i = 1; i <= 6; i++) cout << p[i] << " "; cout << endl;
perms = postot(perms,qr);
// cout << perms.size() << endl;
if(perms.size() == 1) break;
}
auto p = perms[0];
vector<int> pos(7);
for(int i = 1; i <= 6; i++) pos[p[i]] = i;
auto ansvec = pos;
int ANS[] = {ansvec[1],ansvec[2],ansvec[3],ansvec[4],ansvec[5],ansvec[6]};
answer(ANS);
// /* ... */
// int W[] = {1, 2, 3, 4, 5, 6};
// answer(W);
}
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:12:15: warning: unused parameter 'T' [-Wunused-parameter]
12 | void init(int T) {
| ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:151:63: warning: conversion from 'std::chrono::duration<long int, std::ratio<1, 1000000000> >::rep' {aka 'long int'} to 'unsigned int' may change value [-Wconversion]
151 | srand(chrono::system_clock::now().time_since_epoch().count());
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
scales.cpp:175:25: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
175 | mx = max({p1.size(),p2.size(),p3.size()});
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:160:42: warning: 'resp1' may be used uninitialized in this function [-Wmaybe-uninitialized]
160 | qrnew = {3,4,5,6,(resp1 == 1 ? 2 : 1)};
| ~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
972 KB |
Output is correct |
| 2 |
Correct |
70 ms |
848 KB |
Output is correct |
| 3 |
Correct |
74 ms |
792 KB |
Output is correct |
| 4 |
Correct |
65 ms |
604 KB |
Output is correct |
| 5 |
Correct |
70 ms |
860 KB |
Output is correct |
| 6 |
Correct |
65 ms |
756 KB |
Output is correct |
| 7 |
Correct |
69 ms |
740 KB |
Output is correct |
| 8 |
Correct |
65 ms |
708 KB |
Output is correct |
| 9 |
Correct |
59 ms |
604 KB |
Output is correct |
| 10 |
Correct |
72 ms |
780 KB |
Output is correct |
| 11 |
Correct |
68 ms |
780 KB |
Output is correct |
| 12 |
Correct |
69 ms |
852 KB |
Output is correct |
| 13 |
Correct |
68 ms |
820 KB |
Output is correct |
| 14 |
Correct |
68 ms |
600 KB |
Output is correct |
| 15 |
Correct |
66 ms |
756 KB |
Output is correct |
| 16 |
Correct |
78 ms |
1148 KB |
Output is correct |
| 17 |
Correct |
74 ms |
712 KB |
Output is correct |
| 18 |
Correct |
67 ms |
748 KB |
Output is correct |
| 19 |
Correct |
70 ms |
656 KB |
Output is correct |
| 20 |
Correct |
73 ms |
600 KB |
Output is correct |
| 21 |
Correct |
73 ms |
784 KB |
Output is correct |
| 22 |
Correct |
71 ms |
824 KB |
Output is correct |
| 23 |
Correct |
70 ms |
668 KB |
Output is correct |
| 24 |
Correct |
69 ms |
664 KB |
Output is correct |
| 25 |
Correct |
68 ms |
604 KB |
Output is correct |
| 26 |
Correct |
62 ms |
788 KB |
Output is correct |
| 27 |
Correct |
83 ms |
748 KB |
Output is correct |
| 28 |
Correct |
80 ms |
824 KB |
Output is correct |
| 29 |
Correct |
75 ms |
852 KB |
Output is correct |
| 30 |
Correct |
66 ms |
612 KB |
Output is correct |
| 31 |
Correct |
72 ms |
736 KB |
Output is correct |
| 32 |
Correct |
64 ms |
600 KB |
Output is correct |
| 33 |
Correct |
72 ms |
848 KB |
Output is correct |
| 34 |
Correct |
61 ms |
772 KB |
Output is correct |
| 35 |
Correct |
71 ms |
852 KB |
Output is correct |
| 36 |
Correct |
77 ms |
848 KB |
Output is correct |
| 37 |
Correct |
64 ms |
740 KB |
Output is correct |
| 38 |
Correct |
63 ms |
604 KB |
Output is correct |
| 39 |
Correct |
69 ms |
640 KB |
Output is correct |
| 40 |
Correct |
68 ms |
740 KB |
Output is correct |
