| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 93879 |
2019-01-12T18:39:43 Z |
cki86201 |
Scales (IOI15_scales) |
C++11 |
|
478 ms |
888 KB |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include "scales.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;
vector <int> perms[730];
vector< vector <int> > el;
int qsave[150][730];
int get_query(vector <int> q, vector<int> r) {
int cmd = q[0];
int a[3] = {r[q[1]], r[q[2]], r[q[3]]};
sort(a, a+3);
if(cmd <= 3) {
int val = a[1];
if(cmd == 1) val = a[2];
else if(cmd == 2) val = a[0];
for(int i=1;i<=3;i++) if(r[q[i]] == val) return i - 1;
}
else {
int val = -1;
for(int i=0;i<3;i++) if(a[i] > r[q[4]]) {
val = a[i]; break;
}
if(val == -1) val = a[0];
for(int i=1;i<=3;i++) if(r[q[i]] == val) return i - 1;
}
return -1;
}
int callq(vector <int> q) {
int r = -1;
if(q[0] == 1) r = getHeaviest(q[1] + 1, q[2] + 1, q[3] + 1) - 1;
else if(q[0] == 2) r = getLightest(q[1] + 1, q[2] + 1, q[3] + 1) - 1;
else if(q[0] == 3) r = getMedian(q[1] + 1, q[2] + 1, q[3] + 1) - 1;
else r = getNextLightest(q[1] + 1, q[2] + 1, q[3] + 1, q[4] + 1) - 1;
for(int i=1;i<=3;i++) if(q[i] == r) return i-1;
return -1;
}
void init(int T) {
vector <int> v = {0,1,2,3,4,5};
int c = 0;
do {
perms[c++] = v;
} while(next_permutation(all(v)));
rep(i,6) rep(j,i) rep(k,j) {
rep(c,3) el.push_back({c+1, k, j, i});
rep(u,6) if(u != i && u != j && u != k) el.push_back({4, k, j, i, u});
}
rep(i, 120) rep(j, 720) {
qsave[i][j] = get_query(el[i], perms[j]);
}
}
int get_next(const vector <int> &X) {
int mn = 1e9;
vector <int> ml;
rep(i, 120) {
int cnt[3] = {};
for(int e : X) cnt[qsave[i][e]]++;
sort(cnt, cnt+3);
if(mn > cnt[2]) {
mn = cnt[2]; ml.clear(); ml.pb(i);
}
else if(mn == cnt[2]) {
ml.pb(i);
}
}
if(mn == 1) return ml[0];
mn = 1e9;
int x = -1;
for(int i : ml) {
vector <int> W[3];
for(int e : X) W[qsave[i][e]].pb(e);
int cnt[3] = {};
rep(k, 3) cnt[k] = 1e9;
rep(k, 3) {
rep(j, 120) {
int r[3] = {};
for(int f : W[k]) r[qsave[j][f]]++;
sort(r,r+3);
if(cnt[k] > r[2]) cnt[k] = r[2];
}
}
sort(cnt, cnt+3);
if(mn > cnt[2]) mn = cnt[2], x = i;
}
return x;
}
void fix(vector <int> &X, int cn, int ex) {
vector <int> Y;
for(int e : X) if(qsave[cn][e] == ex) Y.pb(e);
X = Y;
}
void orderCoins() {
vector <int> now;
rep(i, 720) now.pb(i);
while(szz(now) > 1) {
int v = get_next(now);
int a = callq(el[v]);
fix(now, v, a);
}
int ans[6] = {};
rep(i, 6) ans[perms[now[0]][i]] = i + 1;
answer(ans);
}
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:73:13: warning: declaration of 'c' shadows a previous local [-Wshadow]
rep(c,3) el.push_back({c+1, k, j, i});
^
scales.cpp:27:26: note: in definition of macro 'rep'
#define rep(i,n) for(int i=0;i<n;i++)
^
scales.cpp:68:9: note: shadowed declaration is here
int c = 0;
^
scales.cpp:66:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
346 ms |
772 KB |
Output is correct |
| 2 |
Correct |
327 ms |
888 KB |
Output is correct |
| 3 |
Correct |
345 ms |
760 KB |
Output is correct |
| 4 |
Correct |
323 ms |
760 KB |
Output is correct |
| 5 |
Correct |
318 ms |
760 KB |
Output is correct |
| 6 |
Correct |
320 ms |
760 KB |
Output is correct |
| 7 |
Correct |
342 ms |
888 KB |
Output is correct |
| 8 |
Correct |
478 ms |
888 KB |
Output is correct |
| 9 |
Correct |
326 ms |
888 KB |
Output is correct |
| 10 |
Correct |
332 ms |
760 KB |
Output is correct |
| 11 |
Correct |
325 ms |
760 KB |
Output is correct |
| 12 |
Correct |
333 ms |
760 KB |
Output is correct |
| 13 |
Correct |
330 ms |
888 KB |
Output is correct |
| 14 |
Correct |
441 ms |
760 KB |
Output is correct |
| 15 |
Correct |
329 ms |
888 KB |
Output is correct |
| 16 |
Correct |
344 ms |
860 KB |
Output is correct |
| 17 |
Correct |
321 ms |
888 KB |
Output is correct |
| 18 |
Correct |
346 ms |
888 KB |
Output is correct |
| 19 |
Correct |
327 ms |
772 KB |
Output is correct |
| 20 |
Correct |
342 ms |
888 KB |
Output is correct |
| 21 |
Correct |
333 ms |
732 KB |
Output is correct |
| 22 |
Correct |
330 ms |
764 KB |
Output is correct |
| 23 |
Correct |
325 ms |
760 KB |
Output is correct |
| 24 |
Correct |
321 ms |
760 KB |
Output is correct |
| 25 |
Correct |
342 ms |
764 KB |
Output is correct |
| 26 |
Correct |
331 ms |
760 KB |
Output is correct |
| 27 |
Correct |
337 ms |
888 KB |
Output is correct |
| 28 |
Correct |
335 ms |
820 KB |
Output is correct |
| 29 |
Correct |
322 ms |
760 KB |
Output is correct |
| 30 |
Correct |
332 ms |
760 KB |
Output is correct |
| 31 |
Correct |
334 ms |
760 KB |
Output is correct |
| 32 |
Correct |
321 ms |
772 KB |
Output is correct |
| 33 |
Correct |
346 ms |
760 KB |
Output is correct |
| 34 |
Correct |
324 ms |
888 KB |
Output is correct |
| 35 |
Correct |
330 ms |
888 KB |
Output is correct |
| 36 |
Correct |
317 ms |
760 KB |
Output is correct |
| 37 |
Correct |
341 ms |
888 KB |
Output is correct |
| 38 |
Correct |
321 ms |
760 KB |
Output is correct |
| 39 |
Correct |
319 ms |
760 KB |
Output is correct |
| 40 |
Correct |
372 ms |
760 KB |
Output is correct |
