# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
23840 |
2017-05-26T14:46:13 Z |
sampriti |
Scales (IOI15_scales) |
C++14 |
|
29 ms |
2404 KB |
#include "scales.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
using namespace std;
const int HEIGHT = 6;
vector<int> perms[720];
vector<vector<int> > ops;
int precalc[720][120];
int optima[HEIGHT + 1];
int best[HEIGHT][720];
int _getHeaviest(vector<int>& arr, int A, int B, int C) {
vector<int> arr2 = {arr[A], arr[B], arr[C]};
sort(arr2.begin(), arr2.end());
int ans = arr2[2];
if(ans == arr[A]) return A;
else if(ans == arr[B]) return B;
return C;
}
int _getLightest(vector<int>& arr, int A, int B, int C) {
vector<int> arr2 = {arr[A], arr[B], arr[C]};
sort(arr2.begin(), arr2.end());
int ans = arr2[0];
if(ans == arr[A]) return A;
else if(ans == arr[B]) return B;
return C;
}
int _getMedian(vector<int>& arr, int A, int B, int C) {
vector<int> arr2 = {arr[A], arr[B], arr[C]};
sort(arr2.begin(), arr2.end());
int ans = arr2[1];
if(ans == arr[A]) return A;
else if(ans == arr[B]) return B;
return C;
}
int _getNextLightest(vector<int>& arr, int A, int B, int C, int D) {
vector<int> arr2;
if(arr[A] > arr[D]) arr2.push_back(arr[A]);
if(arr[B] > arr[D]) arr2.push_back(arr[B]);
if(arr[C] > arr[D]) arr2.push_back(arr[C]);
if(arr2.empty()) arr2 = {arr[A], arr[B], arr[C]};
sort(arr2.begin(), arr2.end());
int ans = arr2[0];
if(ans == arr[A]) return A;
else if(ans == arr[B]) return B;
return C;
}
int call(int type, int A, int B, int C, int D = 0) {
A++; B++; C++; D++;
if(type == 0) {
return getHeaviest(A, B, C) - 1;
}
else if(type == 1) {
return getLightest(A, B, C) - 1;
}
else if(type == 2) {
return getMedian(A, B, C) - 1;
}
else {
return getNextLightest(A, B, C, D) - 1;
}
}
bool build(int layer, vector<int>& cands) {
if(layer == HEIGHT) return true;
for(int j = 0; j < ops.size(); j++) {
vector<int> split[6];
for(int i: cands) {
split[precalc[i][j]].push_back(i);
}
bool pos = true;
for(int k = 0; k < 6; k++) {
if(split[k].size() > optima[layer + 1]) pos = false;
}
if(!pos) continue;
for(int k = 0; k < 6; k++) {
if(split[k].size() == 0) continue;
pos &= build(layer + 1, split[k]);
if(!pos) break;
}
if(pos) {
best[layer][cands[0]] = j;
return true;
}
}
return false;
}
void init(int T) {
perms[0] = {1, 2, 3, 4, 5, 6};
for(int i = 1; i < 720; i++) {
perms[i] = perms[i - 1];
next_permutation(perms[i].begin(), perms[i].end());
}
for(int i = 0; i < 720; i++) {
ops.clear();
for(int j = 0; j < 6; j++) {
for(int k = j + 1; k < 6; k++) {
for(int l = k + 1; l < 6; l++) {
precalc[i][ops.size()] = _getHeaviest(perms[i], j, k, l);
ops.push_back({0, j, k, l});
}
}
}
for(int j = 0; j < 6; j++) {
for(int k = j + 1; k < 6; k++) {
for(int l = k + 1; l < 6; l++) {
precalc[i][ops.size()] = _getLightest(perms[i], j, k, l);
ops.push_back({1, j, k, l});
}
}
}
for(int j = 0; j < 6; j++) {
for(int k = j + 1; k < 6; k++) {
for(int l = k + 1; l < 6; l++) {
precalc[i][ops.size()] = _getMedian(perms[i], j, k, l);
ops.push_back({2, j, k, l});
}
}
}
for(int j = 0; j < 6; j++) {
for(int k = j + 1; k < 6; k++) {
for(int l = k + 1; l < 6; l++) {
for(int m = 0; m < 6; m++) {
if(m == j || m == k || m == l) continue;
precalc[i][ops.size()] = _getNextLightest(perms[i], j, k, l, m);
ops.push_back({3, j, k, l, m});
}
}
}
}
}
optima[HEIGHT] = 1;
for(int i = HEIGHT - 1; i >= 0; i--) {
optima[i] = optima[i + 1] * 3;
}
vector<int> cands;
for(int i = 0; i < 720; i++) cands.push_back(i);
assert(build(0, cands));
}
int solve(int layer, vector<int> cands) {
if(layer == HEIGHT) return cands[0];
int curr = best[layer][cands[0]];
int res = call(ops[curr][0], ops[curr][1], ops[curr][2], ops[curr][3], ops[curr][4]);
vector<int> nxt;
for(int i: cands) {
if(precalc[i][curr] == res) nxt.push_back(i);
}
return solve(layer + 1, nxt);
}
void orderCoins() {
vector<int> cands;
for(int i = 0; i < 720; i++) cands.push_back(i);
int id = solve(0, cands);
int *ans = new int[6];
for(int i = 0; i < 6; i++) {
ans[perms[id][i] - 1] = i + 1;
}
answer(ans);
}
Compilation message
scales.cpp: In function 'bool build(int, std::vector<int>&)':
scales.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < ops.size(); j++) {
^
scales.cpp:85:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(split[k].size() > optima[layer + 1]) pos = false;
^
scales.cpp: At global scope:
scales.cpp:103:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T) {
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
2404 KB |
Output is correct |
2 |
Correct |
16 ms |
2404 KB |
Output is correct |
3 |
Correct |
16 ms |
2404 KB |
Output is correct |
4 |
Correct |
13 ms |
2404 KB |
Output is correct |
5 |
Correct |
16 ms |
2404 KB |
Output is correct |
6 |
Correct |
19 ms |
2404 KB |
Output is correct |
7 |
Correct |
16 ms |
2404 KB |
Output is correct |
8 |
Correct |
16 ms |
2404 KB |
Output is correct |
9 |
Correct |
16 ms |
2404 KB |
Output is correct |
10 |
Correct |
19 ms |
2404 KB |
Output is correct |
11 |
Correct |
19 ms |
2404 KB |
Output is correct |
12 |
Correct |
16 ms |
2404 KB |
Output is correct |
13 |
Correct |
16 ms |
2404 KB |
Output is correct |
14 |
Correct |
19 ms |
2404 KB |
Output is correct |
15 |
Correct |
19 ms |
2404 KB |
Output is correct |
16 |
Correct |
19 ms |
2404 KB |
Output is correct |
17 |
Correct |
19 ms |
2404 KB |
Output is correct |
18 |
Correct |
19 ms |
2404 KB |
Output is correct |
19 |
Correct |
19 ms |
2404 KB |
Output is correct |
20 |
Correct |
16 ms |
2404 KB |
Output is correct |
21 |
Correct |
16 ms |
2404 KB |
Output is correct |
22 |
Correct |
29 ms |
2404 KB |
Output is correct |
23 |
Correct |
26 ms |
2404 KB |
Output is correct |
24 |
Correct |
16 ms |
2404 KB |
Output is correct |
25 |
Correct |
29 ms |
2404 KB |
Output is correct |
26 |
Correct |
19 ms |
2404 KB |
Output is correct |
27 |
Correct |
23 ms |
2404 KB |
Output is correct |
28 |
Correct |
16 ms |
2404 KB |
Output is correct |
29 |
Correct |
16 ms |
2404 KB |
Output is correct |
30 |
Correct |
16 ms |
2404 KB |
Output is correct |
31 |
Correct |
16 ms |
2404 KB |
Output is correct |
32 |
Correct |
16 ms |
2404 KB |
Output is correct |
33 |
Correct |
16 ms |
2404 KB |
Output is correct |
34 |
Correct |
16 ms |
2404 KB |
Output is correct |
35 |
Correct |
16 ms |
2404 KB |
Output is correct |
36 |
Correct |
16 ms |
2404 KB |
Output is correct |
37 |
Correct |
19 ms |
2404 KB |
Output is correct |
38 |
Correct |
19 ms |
2404 KB |
Output is correct |
39 |
Correct |
16 ms |
2404 KB |
Output is correct |
40 |
Correct |
23 ms |
2404 KB |
Output is correct |