| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 58064 | qkxwsm | Scales (IOI15_scales) | C++17 | 16 ms | 1268 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 "scales.h"
#include <bits/stdc++.h>
using namespace std;
template<class T>
void ckmin(T &a, T b)
{
a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
a = max(a, b);
}
long long randomize(long long mod)
{
return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;
const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-20;
#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
long long normalize(long long x, long long mod = INF)
{
return (((x % mod) + mod) % mod);
}
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//bad stuff
//#define _MAXN 6
//#define _MAX_ANSWER_CALLS 1
//static int _ind[_MAXN];
//static int _numQueries;
//int bads = 0;
//
//void answer(int W[]) {
// // cout << _numQueries << " queries:";
// // for (int i = 0; i < 6; i++)
// // {
// // cout << ' ' << W[i];
// // }
// // cout << endl;
// // cout << _numQueries << " OK\n";
// if (_numQueries > 6)
// {
// // cerr << "hi\n";
// bads++;
// }
// _numQueries = 0;
//}
//
//}
//end bad stuff
int perm[720][6];
bool dead[720];
int ret3[720][3][20], ret[720][20][6];
int choices[20][3] = {{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 2, 6}, {1, 3, 4}, {1, 3, 5}, {1, 3, 6}, {1, 4, 5}, {1, 4, 6}, {1, 5, 6}, {2, 3, 4}, {2, 3, 5}, {2, 3, 6}, {2, 4, 5}, {2, 4, 6}, {2, 5, 6}, {3, 4, 5}, {3, 4, 6}, {3, 5, 6}, {4, 5, 6}};
int badidx[] = {103, 108, 109, 114, 291, 292, 293, 297, 298, 299, 303, 304, 305, 309, 310, 311, 411, 412, 413, 417, 418, 419, 423, 424, 425, 429, 430, 431, 607, 612, 613, 618, 634, 635, 640, 641};
bool badflag[720];
//BEGIN SKETCH
int getmedian(int A, int B, int C, int idx) {
if (perm[idx][B] < perm[idx][A] && perm[idx][A] < perm[idx][C])
return A;
if (perm[idx][C] < perm[idx][A] && perm[idx][A] < perm[idx][B])
return A;
if (perm[idx][A] < perm[idx][B] && perm[idx][B] < perm[idx][C])
return B;
if (perm[idx][C] < perm[idx][B] && perm[idx][B] < perm[idx][A])
return B;
return C;
}
int getheaviest(int A, int B, int C, int idx) {
if (perm[idx][A] > perm[idx][B] && perm[idx][A] > perm[idx][C])
return A;
if (perm[idx][B] > perm[idx][A] && perm[idx][B] > perm[idx][C])
return B;
return C;
}
int getlightest(int A, int B, int C, int idx) {
if (perm[idx][A] < perm[idx][B] && perm[idx][A] < perm[idx][C])
return A;
if (perm[idx][B] < perm[idx][A] && perm[idx][B] < perm[idx][C])
return B;
return C;
}
int getnextlightest(int A, int B, int C, int D, int idx) {
int allLess = 1;
if (D == A || D == B || D == C) return 6;
if (perm[idx][A] > perm[idx][D] || perm[idx][B] > perm[idx][D] || perm[idx][C] > perm[idx][D])
allLess = 0;
if (allLess == 1) {
if (perm[idx][A] < perm[idx][B] && perm[idx][A] < perm[idx][C])
return A;
if (perm[idx][B] < perm[idx][A] && perm[idx][B] < perm[idx][C])
return B;
return C;
}
if (perm[idx][A] > perm[idx][D]) {
if ((perm[idx][A] < perm[idx][B] || perm[idx][B] < perm[idx][D]) && (perm[idx][A] < perm[idx][C] || perm[idx][C] < perm[idx][D]))
return A;
}
if (perm[idx][B] > perm[idx][D]) {
if ((perm[idx][B] < perm[idx][A] || perm[idx][A] < perm[idx][D]) && (perm[idx][B] < perm[idx][C] || perm[idx][C] < perm[idx][D]))
return B;
}
return C;
}
//END SKETCH
vector<int> v;
int ans[6], ansidx;
void init(int T)
{
srand(time(0));
for (int x : badidx)
{
badflag[x] = true;
}
for (int i = 0; i < 6; i++)
{
perm[0][i] = i;
}
for (int i = 0; i < 20; i++)
{
for (int j = 0; j < 3; j++)
{
choices[i][j]--;
}
}
for (int i = 1; i < 720; i++)
{
for (int j = 0; j < 6; j++)
{
perm[i][j] = perm[i - 1][j];
}
next_permutation(perm[i], perm[i] + 6);
}
// cerr << getmedian(3, 4, 5, 1) << endl;
for (int i = 0; i < 720; i++)
{
for (int j = 0; j < 20; j++)
{
ret3[i][0][j] = getmedian(choices[j][0], choices[j][1], choices[j][2], i);
ret3[i][1][j] = getheaviest(choices[j][0], choices[j][1], choices[j][2], i);
ret3[i][2][j] = getlightest(choices[j][0], choices[j][1], choices[j][2], i);
for (int k = 0; k < 6; k++)
{
ret[i][j][k] = getnextlightest(choices[j][0], choices[j][1], choices[j][2], k, i);
}
// cout << ret3[i][0][j] << endl;
}
}
}
void orderCoins()
{
for (int i = 0; i < 6; i++)
{
ans[i] = i;
}
for (int i = 0; i < 720; i++)
{
dead[i] = false;
}
// cerr << "hi\n";
while(true)
{
int cnt3[3][20][6], cnt[20][6][6];
memset(cnt3, 0, sizeof(cnt3));
memset(cnt, 0, sizeof(cnt));
//life is too short for some things...
for (int i = 0; i < 720; i++)
{
if (dead[i])
{
continue;
}
for (int j = 0; j < 20; j++)
{
cnt3[0][j][ret3[i][0][j]] += 2;
cnt3[1][j][ret3[i][1][j]] += 2;
cnt3[2][j][ret3[i][2][j]] += 2;
if (badflag[i])
{
cnt3[0][j][ret3[i][0][j]] += 1;
cnt3[1][j][ret3[i][1][j]] += 1;
cnt3[2][j][ret3[i][2][j]] += 1;
}
for (int k = 0; k < 6; k++)
{
if (ret[i][j][k] == 6)
{
continue;
}
cnt[j][k][ret[i][j][k]] += 2;
if (badflag[i])
{
cnt[j][k][ret[i][j][k]] += 1;
}
}
}
}
ll best = LLINF;
bool flag; int x, y;
vector<pair<bool, pii> > vec;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 20; j++)
{
ll cur = 0;
for (int k = 0; k < 6; k++)
{
cur += 1ll * cnt3[i][j][k] * cnt3[i][j][k];
// ckmax(cur, cnt3[i][j][k]);
}
// cerr << cur << ' ' << i << ' '<< j << endl;
if (cur < best)
{
best = cur;
vec.clear();
vec.PB(MP(false, MP(i, j)));
// flag = false; x = i; y = j;
}
else if (cur == best)
{
vec.PB(MP(false, MP(i, j)));
}
}
}
for (int i = 0; i < 20; i++)
{
for (int j = 0; j < 6; j++)
{
if (ret[0][i][j] == 6) continue;
ll cur = 0;
for (int k = 0; k < 6; k++)
{
cur += 1ll * cnt[i][j][k] * cnt[i][j][k];
// ckmax(cur, cnt[i][j][k]);
}
if (cur < best)
{
best = cur;
vec.clear();
vec.PB(MP(true, MP(i, j)));
// flag = true; x = i; y = j;
}
else if (cur == best)
{
vec.PB(MP(true, MP(i, j)));
}
}
}
int rand_idx = 0;
flag = vec[rand_idx].fi; x = vec[rand_idx].se.fi; y = vec[rand_idx].se.se;
// debug(best); debug(flag); debug(x); debug(y);
int res;
if (flag)
{
res = getNextLightest(choices[x][0] + 1, choices[x][1] + 1, choices[x][2] + 1, y + 1);
res--;
for (int i = 0; i < 720; i++)
{
if (ret[i][x][y] != res)
{
dead[i] = true;
}
}
}
else
{
if (x == 0)
{
res = getMedian(choices[y][0] + 1, choices[y][1] + 1, choices[y][2] + 1);
}
if (x == 1)
{
res = getHeaviest(choices[y][0] + 1, choices[y][1] + 1, choices[y][2] + 1);
}
if (x == 2)
{
res = getLightest(choices[y][0] + 1, choices[y][1] + 1, choices[y][2] + 1);
}
res--;
for (int i = 0; i < 720; i++)
{
if (ret3[i][x][y] != res)
{
dead[i] = true;
}
}
}
int alives = 0;
for (int i = 0; i < 720; i++)
{
if (!dead[i])
{
alives++;
ansidx = i;
}
}
if (alives == 1)
{
break;
}
}
for (int i = 0; i < 6; i++)
{
ans[perm[ansidx][i]] = i + 1;
}
//all 90 possible moves...
//getMedian, getHeaviest, getLightest, getNextLightest
answer(ans);
}
//int main()
//{
// int T;
// // cin >> T;
// T = 720;
// init(T);
// for (int tc = 0; tc < T; tc++)
// {
// for (int i = 0; i < 6; i++)
// {
// _ind[i] = i;
// }
// for (int i = 0; i < tc; i++)
// {
// next_permutation(_ind, _ind + 6);
// }
// int wasbads = bads;
// orderCoins();
// int nowbads = bads;
//// if (wasbads != nowbads)
//// {
//// cerr << tc << ", ";
// // for (int i = 0; i < 6; i++)
// // {
// // cerr << _ind[i] << ' ';
// // }
// // cerr << endl;
//// }
// // orderCoins();
// }
// debug(bads);
//}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||