| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 755631 | Theo830 | Scales (IOI15_scales) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#include "scales.h"
void init(int T) {
}
void orderCoins() {
vector<int>P;
f(i,0,6){
P.pb(i+1);
}
set<vector<int> >ex;
do{
ex.insert(P);
}
while(next_permutation(all(P)));
while(ex.size() > 1){
ll t = 0,a,b,c,d,ans = 0;
f(i,0,6){
f(j,i+1,6){
f(k,j+1,6){
ll res = INF;
ll cur = 0;
for(auto x:ex){
if(x[i] < x[j] && x[i] < x[k]){
}
else{
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
if(x[j] < x[i] && x[j] < x[k]){
}
else{
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
if(x[k] < x[i] && x[k] < x[j]){
}
else{
cur++;
}
}
res = min(res,cur);
if(ans < res){
ans = res;
t = 0;
a = i;
b = j;
c = k;
}
}
}
}
f(i,0,6){
f(j,i+1,6){
f(k,j+1,6){
ll res = INF;
ll cur = 0;
for(auto x:ex){
if(x[i] > x[j] && x[i] > x[k]){
}
else{
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
if(x[j] > x[i] && x[j] > x[k]){
}
else{
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
if(x[k] > x[i] && x[k] > x[j]){
}
else{
cur++;
}
}
res = min(res,cur);
if(ans < res){
ans = res;
t = 2;
a = i;
b = j;
c = k;
}
}
}
}
f(i,0,6){
f(j,i+1,6){
f(k,j+1,6){
f(u,0,6){
if(u != i && u != j && u != k){
ll res = INF;
ll cur = 0;
for(auto x:ex){
vector<ii>ar;
ar.pb(ii(x[i],i));
ar.pb(ii(x[j],j));
ar.pb(ii(x[u],u));
ar.pb(ii(x[k],k));
bool ok;
if(ar.back().S == u){
ok = ar[0].S == i;
}
else{
f(r,0,3){
if(ar[r].S == u){
ok = ar[r+1].S == i;
break;
}
}
}
if(!ok){
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
vector<ii>ar;
ar.pb(ii(x[i],i));
ar.pb(ii(x[j],j));
ar.pb(ii(x[u],u));
ar.pb(ii(x[k],k));
bool ok;
if(ar.back().S == u){
ok = ar[0].S == j;
}
else{
f(r,0,3){
if(ar[r].S == u){
ok = ar[r+1].S == j;
break;
}
}
}
if(!ok){
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
vector<ii>ar;
ar.pb(ii(x[i],i));
ar.pb(ii(x[j],j));
ar.pb(ii(x[u],u));
ar.pb(ii(x[k],k));
bool ok;
if(ar.back().S == u){
ok = ar[0].S == k;
}
else{
f(r,0,3){
if(ar[r].S == u){
ok = ar[r+1].S == k;
break;
}
}
}
if(!ok){
cur++;
}
}
res = min(res,cur);
if(ans < res){
ans = res;
t = 3;
a = i;
b = j;
c = k;
d = u;
}
}
}
}
}
}
a++;
b++;
c++;
set<vector<int> >fkale;
if(t == 0){
ll pos = getLightest(a,b,c);
a--;
b--;
c--;
pos--;
for(auto x:ex){
if(x[pos] <= x[a] && x[pos] <= x[b] && x[pos] <= x[c]){
}
else{
fkale.insert(x);
}
}
}
else if(t == 1){
ll pos = getMedian(a,b,c);
a--;
b--;
c--;
pos--;
for(auto x:ex){
ll posoi = (x[pos] > x[a]) + (x[pos] > x[b]) + (x[pos] > x[c]);
if(posoi != 1){
fkale.insert(x);
}
}
}
else if(t == 2){
ll pos = getHeaviest(a,b,c);
a--;
b--;
c--;
pos--;
for(auto x:ex){
if(x[pos] >= x[a] && x[pos] >= x[b] && x[pos] >= x[c]){
}
else{
fkale.insert(x);
}
}
}
else{
}
for(auto x:fkale){
ex.erase(x);
}
}
vll a = (*ex.begin());
f(i,0,6){
W[a[i]-1] = i+1;
}
answer(W);
}