| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 729562 | Vu_CG_Coder | Scales (IOI15_scales) | C++14 | 2 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.
/* [Author : Hoang Duy Vu] - THPT Chuyen Nguyen Du */
//#pragma GCC optimize(" unroll-loops")
//#pragma gcc optimize("Ofast")
//#pragma GCC optimization("Ofast")
//#pragma optimize(Ofast)
#include "scales.h"
#include <bits/stdc++.h>
#define All(x) (x).begin(),(x).end()
#define ll long long
#define C make_pair
#define fi first
#define se second
#define two second.first
#define thr second.second
#define TASK "txt"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) {
if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) {
if (res > val) { res = val; return true; } return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int LOG = 20;
const int INF = 1e9 + 7;
const ll LNF = 1e18 + 7;
const int mod = 1e9 + 7;
const int N = 10;
//unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
//mt19937 Rand(seed);
struct node
{
int a , b , c , id;
node() {}
node(int a , int b , int c , int id): a(a), b(b), c(c), id(id) {}
};
vector <vector<int> > f[11];
vector <vector<int> > p;
vector <node> local;
vector <pair<vector<int>,int> > value;
int id = 0;
int cnt;
int val[N];
// int getLightest(int a , int b , int c)
// {
// for (int i = 0 ; i < 5 ; i++)
// if (val[i] == a || val[i] == b || val[i] == c) return val[i];
// }
// int getHeaviest(int a , int b , int c)
// {
// for (int i = 5 ; i >= 0 ; i--)
// if (val[i] == a || val[i] == b || val[i] == c) return val[i];
// }
// int getMedian(int a , int b , int c)
// {
// int d = 0;
// for (int i = 0 ; i < 5 ; i++)
// if (val[i] == a || val[i] == b || val[i] == c)
// {
// d++;
// if (d == 2) return val[i];
// }
// }
// void answer(int x[]) {
// for (int i = 0 ; i < 6 ; i++) cout << x[i] << " ";
// cout << "\n";
// }
void init(int T) {
}
int light(int pos , int a , int b , int c,int o)
{
vector <int> x;
x.push_back(a);
x.push_back(b);
x.push_back(c);
int d = 0;
for (int i = 0; i < f[id - 1].size() ; i++)
if (min(f[id - 1][i][a],min(f[id - 1][i][b],f[id - 1][i][c])) == f[id - 1][i][x[pos]])
{
d++;
if (o) f[id].push_back(f[id - 1][i]);
}
return d;
}
int Heaviest(int pos , int a , int b , int c,int o)
{
vector <int> x;
x.push_back(a);
x.push_back(b);
x.push_back(c);
int d = 0;
for (int i = 0; i < f[id - 1].size() ; i++)
if (max(f[id - 1][i][a],max(f[id - 1][i][b],f[id - 1][i][c])) == f[id - 1][i][x[pos]])
{
d++;
if (o) f[id].push_back(f[id - 1][i]);
}
return d;
}
int Median(int pos , int a , int b , int c,int o)
{
vector <int> x;
x.push_back(a);
x.push_back(b);
x.push_back(c);
int d = 0;
for (int i = 0; i < f[id - 1].size() ; i++)
if (max(f[id - 1][i][a],max(f[id - 1][i][b],f[id - 1][i][c])) != f[id - 1][i][x[pos]] &&
min(f[id - 1][i][a],min(f[id - 1][i][b],f[id - 1][i][c])) != f[id - 1][i][x[pos]])
{
d++;
if (o) f[id].push_back(f[id - 1][i]);
}
return d;
}
void orderCoins() {
int W[] = {1,2,3,4,5,6};
vector <int> k;
for (int i = 0 ; i < 6 ; i++) k.push_back(i);
for (int i = 0 ; i < 11 ; i++) f[i].clear();
cnt = 0;
do
{
f[0].push_back(k);
} while (next_permutation(All(k)));
id = 0;
while (true)
{
int d = 0;
id++;
p.clear();
int cntpos = 0;
local.clear();
value.clear();
for (int a = 0 ; a < 6 ; a++)
for (int b = a + 1; b < 6 ; b++)
for (int c = b + 1; c < 6 ; c++)
{
vector <int> x;
local.push_back(node(a,b,c,0));
x.push_back(light(0,a,b,c,0));
x.push_back(light(1,a,b,c,0));
x.push_back(light(2,a,b,c,0));
value.push_back(C(x,cntpos++));
x.clear();
local.push_back(node(a,b,c,1));
x.push_back(Heaviest(0,a,b,c,0));
x.push_back(Heaviest(1,a,b,c,0));
x.push_back(Heaviest(2,a,b,c,0));
value.push_back(C(x,cntpos++));
x.clear();
local.push_back(node(a,b,c,2));
x.push_back(Median(0,a,b,c,0));
x.push_back(Median(1,a,b,c,0));
x.push_back(Median(2,a,b,c,0));
value.push_back(C(x,cntpos++));
}
for (int i = 0 ; i < cntpos ; i++) sort(All(value[i].fi),greater<int>());
sort(All(value));
int vt = value[0].se;
int a = local[vt].a;
int b = local[vt].b;
int c = local[vt].c;
// cout << local[vt].id << " " << a << " " << b << " " << c << "\n";
if (local[vt].id == 0) {
int ioi = getLightest(a,b,c);
// cout << ioi << "\n";
if (ioi == a) light(0,a,b,c,1);
if (ioi == b) light(1,a,b,c,1);
if (ioi == c) light(2,a,b,c,1);
}
if (local[vt].id == 1) {
int ioi = getHeaviest(a,b,c);
if (ioi == a) Heaviest(0,a,b,c,1);
if (ioi == b) Heaviest(1,a,b,c,1);
if (ioi == c) Heaviest(2,a,b,c,1);
}
if (local[vt].id == 2) {
int ioi = getMedian(a,b,c);
if (ioi == a) Median(0,a,b,c,1);
if (ioi == b) Median(1,a,b,c,1);
if (ioi == c) Median(2,a,b,c,1);
}
// for (vector <int> t : f[id])
// {
// for (int v : t) cout << v << " ";
// cout << "\n";
// }
// cout << id << " " << "\n";
if (f[id].size() == 1) break ;
}
for (int i = 0 ; i < 6 ; i++)
{
for (int j = 0 ; j < 6 ; j++) if (f[id][0][j] == i) W[i] = j;
}
answer(W);
}
// int main()
// {
// ios_base::sync_with_stdio(0);
// cin.tie(NULL); cout.tie(NULL);
// if(fopen(TASK".inp", "r")){
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
// }
// int t;
// cin >> t;
// while (t--)
// {
// for (int i = 0 ; i < 6 ; i++) cin >> val[i];
// orderCoins();
// }
// return 0;
// }
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||