| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 57782 |
2018-07-16T06:08:42 Z |
qkxwsm |
Scales (IOI15_scales) |
C++17 |
|
12 ms |
1252 KB |
#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
//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}};
//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 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));
cnt3[1][18][5] = 0;
//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]]++;
cnt3[1][j][ret3[i][1][j]]++;
cnt3[2][j][ret3[i][2][j]]++;
for (int k = 0; k < 6; k++)
{
if (ret[i][j][k] == 6)
{
continue;
}
cnt[j][k][ret[i][j][k]]++;
}
}
}
int best = 911;
bool flag; int x, y;
vector<pair<bool, pii> > vec;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 20; j++)
{
int cur = 0;
for (int k = 0; k < 6; 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;
int cur = 0;
for (int k = 0; k < 6; 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 = randomize(vec.size());
// 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;
}
//0j, 1j, 2j, j0, j1, j2, j3, j4, j5, j6
}
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)
//// {
//// for (int i = 0; i < 6; i++)
//// {
//// cerr << _ind[i] << ' ';
//// }
//// cerr << endl;
//// }
// // orderCoins();
// }
// debug(bads);
//}
Compilation message
In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (_ghksjhdfkae19ga_ > 1)
^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
for (i = 0; i < 6; i++) {
^~~
scales.cpp: In function 'void init(int)':
scales.cpp:136:12: warning: conversion to 'unsigned int' from 'time_t {aka long int}' may alter its value [-Wconversion]
srand(time(0));
~~~~^~~
scales.cpp:134:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T)
^
scales.cpp: In function 'void orderCoins()':
scales.cpp:261:27: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
int rand_idx = randomize(vec.size());
~~~~~~~~~^~~~~~~~~~~~
scales.cpp:292:7: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
res--;
~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
9 ms |
888 KB |
Output is partially correct |
| 2 |
Partially correct |
9 ms |
976 KB |
Output is partially correct |
| 3 |
Partially correct |
8 ms |
976 KB |
Output is partially correct |
| 4 |
Partially correct |
9 ms |
976 KB |
Output is partially correct |
| 5 |
Correct |
9 ms |
984 KB |
Output is correct |
| 6 |
Correct |
8 ms |
1040 KB |
Output is correct |
| 7 |
Partially correct |
8 ms |
1088 KB |
Output is partially correct |
| 8 |
Correct |
8 ms |
1192 KB |
Output is correct |
| 9 |
Partially correct |
8 ms |
1192 KB |
Output is partially correct |
| 10 |
Partially correct |
9 ms |
1192 KB |
Output is partially correct |
| 11 |
Partially correct |
8 ms |
1192 KB |
Output is partially correct |
| 12 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 13 |
Correct |
8 ms |
1252 KB |
Output is correct |
| 14 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 15 |
Partially correct |
9 ms |
1252 KB |
Output is partially correct |
| 16 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 17 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 18 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 19 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 20 |
Partially correct |
9 ms |
1252 KB |
Output is partially correct |
| 21 |
Partially correct |
10 ms |
1252 KB |
Output is partially correct |
| 22 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 23 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 24 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 25 |
Correct |
8 ms |
1252 KB |
Output is correct |
| 26 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 27 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 28 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 29 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 30 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 31 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 32 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 33 |
Partially correct |
12 ms |
1252 KB |
Output is partially correct |
| 34 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 35 |
Partially correct |
12 ms |
1252 KB |
Output is partially correct |
| 36 |
Partially correct |
9 ms |
1252 KB |
Output is partially correct |
| 37 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 38 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
| 39 |
Partially correct |
9 ms |
1252 KB |
Output is partially correct |
| 40 |
Partially correct |
8 ms |
1252 KB |
Output is partially correct |
