| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 940763 |
2024-03-07T15:24:31 Z |
AdamGS |
Scales (IOI15_scales) |
C++17 |
|
381 ms |
1152 KB |
#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int INF=1e9+7;
struct node {
int typ=-1, A, B, C, D;
int nxta, nxtb, nxtc;
vector<int>P;
};
node puste;
vector<node>V;
void solve(vector<vector<int>>&T, int ind);
int get_hev(vector<int>&T, int A, int B, int C) {
vector<pair<int,int>>P;
P.pb({T[A], A});
P.pb({T[B], B});
P.pb({T[C], C});
sort(all(P));
return P[2].nd;
}
int get_lig(vector<int>&T, int A, int B, int C) {
vector<pair<int,int>>P;
P.pb({T[A], A});
P.pb({T[B], B});
P.pb({T[C], C});
sort(all(P));
return P[0].nd;
}
int get_med(vector<int>&T, int A, int B, int C) {
vector<pair<int,int>>P;
P.pb({T[A], A});
P.pb({T[B], B});
P.pb({T[C], C});
sort(all(P));
return P[1].nd;
}
int get_nxt(vector<int>&T, int A, int B, int C, int D) {
vector<pair<int,int>>P;
P.pb({T[A], A});
P.pb({T[B], B});
P.pb({T[C], C});
sort(all(P));
for(auto i : P) if(i.st>T[D]) return i.nd;
return P[0].nd;
}
void rob(vector<vector<int>>&T, int ind, int typ, int A, int B, int C, int D) {
vector<vector<int>>X, Y, Z;
for(auto i : T) {
int p;
if(typ==0) p=get_hev(i, A, B, C);
if(typ==1) p=get_lig(i, A, B, C);
if(typ==2) p=get_med(i, A, B, C);
if(typ==3) p=get_nxt(i, A, B, C, D);
if(p==A) X.pb(i);
if(p==B) Y.pb(i);
if(p==C) Z.pb(i);
}
V[ind].typ=typ;
V[ind].A=A;
V[ind].B=B;
V[ind].C=C;
V[ind].D=D;
if(X.size()) {
V[ind].nxta=V.size();
V.pb(puste);
solve(X, V[ind].nxta);
}
if(Y.size()) {
V[ind].nxtb=V.size();
V.pb(puste);
solve(Y, V[ind].nxtb);
}
if(Z.size()) {
V[ind].nxtc=V.size();
V.pb(puste);
solve(Z, V[ind].nxtc);
}
}
void solve(vector<vector<int>>&T, int ind) {
if(T.size()==1) V[ind].P=T[0];
if(T.size()<=1) return;
int mi=INF;
rep(A, 6) rep(B, 6) rep(C, 6) if(A!=B && A!=C && B!=C) {
int x=0, y=0, z=0;
for(auto i : T) {
int p=get_hev(i, A, B, C);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
mi=min(mi, max(max(x, y), z));
x=y=z=0;
for(auto i : T) {
int p=get_lig(i, A, B, C);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
mi=min(mi, max(max(x, y), z));
x=y=z=0;
for(auto i : T) {
int p=get_med(i, A, B, C);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
mi=min(mi, max(max(x, y), z));
rep(D, 6) if(A!=D && B!=D && C!=D) {
x=y=z=0;
for(auto i : T) {
int p=get_nxt(i, A, B, C, D);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
mi=min(mi, max(max(x, y), z));
}
}
rep(A, 6) rep(B, 6) rep(C, 6) if(A!=B && A!=C && B!=C) {
int x=0, y=0, z=0;
for(auto i : T) {
int p=get_hev(i, A, B, C);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
if(max(max(x, y), z)==mi) {
rob(T, ind, 0, A, B, C, 0);
return;
}
x=y=z=0;
for(auto i : T) {
int p=get_lig(i, A, B, C);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
if(max(max(x, y), z)==mi) {
rob(T, ind, 1, A, B, C, 0);
return;
}
x=y=z=0;
for(auto i : T) {
int p=get_med(i, A, B, C);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
if(max(max(x, y), z)==mi) {
rob(T, ind, 2, A, B, C, 0);
return;
}
rep(D, 6) if(A!=D && B!=D && C!=D) {
x=y=z=0;
for(auto i : T) {
int p=get_nxt(i, A, B, C, D);
if(p==A) ++x;
if(p==B) ++y;
if(p==C) ++z;
}
if(max(max(x, y), z)==mi) {
rob(T, ind, 3, A, B, C, D);
return;
}
}
}
}
void init(int T) {
V.pb(puste);
vector<vector<int>>P;
vector<int>X;
rep(i, 6) X.pb(i);
do P.pb(X); while(next_permutation(all(X)));
solve(P, 0);
}
void zejdz(int x) {
if(V[x].P.size()==6) {
int ans[6];
rep(i, 6) ans[V[x].P[i]]=i+1;
answer(ans);
return;
}
int p;
if(V[x].typ==0) p=getHeaviest(V[x].A+1, V[x].B+1, V[x].C+1);
if(V[x].typ==1) p=getLightest(V[x].A+1, V[x].B+1, V[x].C+1);
if(V[x].typ==2) p=getMedian(V[x].A+1, V[x].B+1, V[x].C+1);
if(V[x].typ==3) p=getNextLightest(V[x].A+1, V[x].B+1, V[x].C+1, V[x].D+1);
if(p==V[x].A+1) zejdz(V[x].nxta);
if(p==V[x].B+1) zejdz(V[x].nxtb);
if(p==V[x].C+1) zejdz(V[x].nxtc);
}
void orderCoins() {
zejdz(0);
}
Compilation message
scales.cpp: In function 'void rob(std::vector<std::vector<int> >&, int, int, int, int, int, int)':
scales.cpp:69:23: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
69 | V[ind].nxta=V.size();
| ~~~~~~^~
scales.cpp:74:23: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
74 | V[ind].nxtb=V.size();
| ~~~~~~^~
scales.cpp:79:23: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
79 | V[ind].nxtc=V.size();
| ~~~~~~^~
scales.cpp: In function 'void init(int)':
scales.cpp:173:15: warning: unused parameter 'T' [-Wunused-parameter]
173 | void init(int T) {
| ~~~~^
scales.cpp: In function 'void zejdz(int)':
scales.cpp:193:3: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
193 | if(p==V[x].A+1) zejdz(V[x].nxta);
| ^~
scales.cpp: In function 'void rob(std::vector<std::vector<int> >&, int, int, int, int, int, int)':
scales.cpp:61:5: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
61 | if(p==C) Z.pb(i);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
322 ms |
460 KB |
Output is partially correct |
| 2 |
Partially correct |
322 ms |
1036 KB |
Output is partially correct |
| 3 |
Partially correct |
321 ms |
472 KB |
Output is partially correct |
| 4 |
Partially correct |
322 ms |
900 KB |
Output is partially correct |
| 5 |
Partially correct |
321 ms |
592 KB |
Output is partially correct |
| 6 |
Partially correct |
325 ms |
1152 KB |
Output is partially correct |
| 7 |
Partially correct |
322 ms |
700 KB |
Output is partially correct |
| 8 |
Partially correct |
329 ms |
708 KB |
Output is partially correct |
| 9 |
Partially correct |
322 ms |
596 KB |
Output is partially correct |
| 10 |
Partially correct |
342 ms |
596 KB |
Output is partially correct |
| 11 |
Partially correct |
326 ms |
764 KB |
Output is partially correct |
| 12 |
Partially correct |
320 ms |
592 KB |
Output is partially correct |
| 13 |
Partially correct |
327 ms |
476 KB |
Output is partially correct |
| 14 |
Partially correct |
322 ms |
600 KB |
Output is partially correct |
| 15 |
Partially correct |
324 ms |
772 KB |
Output is partially correct |
| 16 |
Partially correct |
331 ms |
480 KB |
Output is partially correct |
| 17 |
Partially correct |
330 ms |
572 KB |
Output is partially correct |
| 18 |
Partially correct |
324 ms |
596 KB |
Output is partially correct |
| 19 |
Partially correct |
332 ms |
920 KB |
Output is partially correct |
| 20 |
Partially correct |
322 ms |
592 KB |
Output is partially correct |
| 21 |
Partially correct |
350 ms |
1064 KB |
Output is partially correct |
| 22 |
Partially correct |
321 ms |
596 KB |
Output is partially correct |
| 23 |
Partially correct |
327 ms |
596 KB |
Output is partially correct |
| 24 |
Partially correct |
322 ms |
636 KB |
Output is partially correct |
| 25 |
Partially correct |
321 ms |
484 KB |
Output is partially correct |
| 26 |
Partially correct |
326 ms |
596 KB |
Output is partially correct |
| 27 |
Partially correct |
353 ms |
632 KB |
Output is partially correct |
| 28 |
Partially correct |
332 ms |
756 KB |
Output is partially correct |
| 29 |
Partially correct |
326 ms |
600 KB |
Output is partially correct |
| 30 |
Partially correct |
324 ms |
728 KB |
Output is partially correct |
| 31 |
Partially correct |
321 ms |
592 KB |
Output is partially correct |
| 32 |
Partially correct |
323 ms |
596 KB |
Output is partially correct |
| 33 |
Partially correct |
323 ms |
592 KB |
Output is partially correct |
| 34 |
Partially correct |
325 ms |
960 KB |
Output is partially correct |
| 35 |
Partially correct |
324 ms |
596 KB |
Output is partially correct |
| 36 |
Partially correct |
381 ms |
596 KB |
Output is partially correct |
| 37 |
Partially correct |
321 ms |
500 KB |
Output is partially correct |
| 38 |
Partially correct |
323 ms |
596 KB |
Output is partially correct |
| 39 |
Partially correct |
324 ms |
512 KB |
Output is partially correct |
| 40 |
Partially correct |
326 ms |
500 KB |
Output is partially correct |
