| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 755620 | Theo830 | Scales (IOI15_scales) | C++17 | 8 ms | 596 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()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
#include "scales.h"
void init(int T) {
}
void orderCoins() {
int W[] = {1, 2, 3, 4, 5, 6};
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 if(x[i] > x[j] && x[i] < x[k]){
}
else{
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
if(x[k] < x[j] && x[k] > x[i]){
}
else if(x[k] > x[j] && x[k] < x[i]){
}
else{
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
if(x[j] < x[i] && x[j] > x[k]){
}
else if(x[j] > x[i] && x[j] < x[k]){
}
else{
cur++;
}
}
res = min(res,cur);
if(ans < res){
ans = res;
t = 1;
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;
}
}
}
}
set<vector<int> >fkale;
if(t == 0){
ll pos = getLightest(a,b,c);
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);
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);
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[i] = a[i];
}
answer(W);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||