| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 30994 |
2017-08-03T06:41:22 Z |
kajebiii |
Scales (IOI15_scales) |
C++14 |
|
113 ms |
2304 KB |
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;
static void __checkQuery(int A, int B, int C, int D) {
if (D == -1) {
if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6)
assert(0);
if (A == B || B == C || A == C)
assert(0);
}
else {
if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6 || D < 1 || D > 6)
assert(0);
if (A == B || A == C || A == D || B == C || B == D || C == D)
assert(0);
}
}
int _getMedian(int A, int B, int C, vector<int> _ind) {
__checkQuery(A, B, C, -1);
A--; B--; C--;
if (_ind[B] < _ind[A] && _ind[A] < _ind[C])
return A + 1;
if (_ind[C] < _ind[A] && _ind[A] < _ind[B])
return A + 1;
if (_ind[A] < _ind[B] && _ind[B] < _ind[C])
return B + 1;
if (_ind[C] < _ind[B] && _ind[B] < _ind[A])
return B + 1;
return C + 1;
}
int _getHeaviest(int A, int B, int C, vector<int> _ind) {
__checkQuery(A, B, C, -1);
A--; B--; C--;
if (_ind[A] > _ind[B] && _ind[A] > _ind[C])
return A + 1;
if (_ind[B] > _ind[A] && _ind[B] > _ind[C])
return B + 1;
return C + 1;
}
int _getLightest(int A, int B, int C, vector<int> _ind) {
__checkQuery(A, B, C, -1);
A--; B--; C--;
if (_ind[A] < _ind[B] && _ind[A] < _ind[C])
return A + 1;
if (_ind[B] < _ind[A] && _ind[B] < _ind[C])
return B + 1;
return C + 1;
}
int _getNextLightest(int A, int B, int C, int D, vector<int> _ind) {
int allLess = 1;
__checkQuery(A, B, C, D);
A--; B--; C--; D--;
if (_ind[A] > _ind[D] || _ind[B] > _ind[D] || _ind[C] > _ind[D])
allLess = 0;
if (allLess == 1) {
if (_ind[A] < _ind[B] && _ind[A] < _ind[C])
return A + 1;
if (_ind[B] < _ind[A] && _ind[B] < _ind[C])
return B + 1;
return C + 1;
}
if (_ind[A] > _ind[D]) {
if ((_ind[A] < _ind[B] || _ind[B] < _ind[D]) && (_ind[A] < _ind[C] || _ind[C] < _ind[D]))
return A + 1;
}
if (_ind[B] > _ind[D]) {
if ((_ind[B] < _ind[A] || _ind[A] < _ind[D]) && (_ind[B] < _ind[C] || _ind[C] < _ind[D]))
return B + 1;
}
return C + 1;
}
vector<vector<int>> Candi;
vector<vector<int>> Qs;
vector<int> cntList[10];
int minV = INF;
vector<pi> His;
map<vector<pi>, int> Mp;
bool isCan(int times, vector<int> cd, bool find) {
if(times < minV) {
minV = times;
// printf("%d\n", times);
}
int n = SZ(cd);
int cnt = 0;
for(int nn=n; nn > 1; nn = (nn+2) / 3, cnt++);
if(cnt > times) return false;
if(times == 0) {
if(find && SZ(cd) > 0) Mp[His] = cd[0];
// for(pi &e : His) printf("[%d %d] ", e.one, e.two); puts("");
return true;
}
for(int cnt : cntList[6-times]) {
vector<int> &v = Qs[cnt];
vector<int> nt[3];
int q = v[0], a = v[1], b = v[2], c = v[3];
int d = -1;
if(q == 3) d = v[4];
for(int x : cd) {
int res = -1;
if(q == 0) res = _getHeaviest(a, b, c, Candi[x]);
if(q == 1) res = _getMedian(a, b, c, Candi[x]);
if(q == 2) res = _getLightest(a, b, c, Candi[x]);
if(q == 3) res = _getNextLightest(a, b, c, d, Candi[x]);
for(int k=0; k<3; k++) if(res == v[k+1]) {
nt[k].push_back(x);
break;
}
}
bool nowCan = true;
for(int k=0; k<3; k++) {
His.push_back(pi(cnt, k));
bool res = isCan(times-1, nt[k], false);
His.pop_back();
if(!res) {
nowCan = false;
break;
}
}
if(nowCan) {
if(times == 6 || find == true) {
Mp[His] = cnt;
for(int k=0; k<3; k++) {
His.push_back(pi(cnt, k));
bool res = isCan(times-1, nt[k], true);
His.pop_back();
}
}
return true;
}
cnt++;
}
return false;
}
void init(int T) {
cntList[0] = vector<int>({0});
cntList[1] = vector<int>({58});
cntList[2] = vector<int>({67, 69, 70, 73, 74, 75, 77, 78, 79});
cntList[3] = vector<int>({7, 10, 26, 29, 41, 44, 47, 50, 53, 56, 63, 76});
cntList[4] = vector<int>({3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 27, 28, 31, 34, 48, 49, 51, 52, 83, 84, 85, 92, 93, 94, 105, 106});
cntList[5] = vector<int>({1, 3, 4, 6, 7, 10, 12, 13, 15, 16, 19, 22, 25, 28, 31, 34, 37, 39, 40, 42, 43, 45, 46, 49, 52, 55});
Candi.clear();
int ch[6]; for(int i=0; i<6; i++) ch[i] = i+1;
do{
Candi.push_back(vector<int>());
for(int i=0; i<6; i++) Candi.back().push_back(ch[i]);
}while(next_permutation(ch, ch+6));
for(int i=0; i<6; i++) ch[i] = (i >= 3);
do{
vector<int> list;
for(int i=0; i<6; i++) if(ch[i]) list.push_back(i);
for(int q=0; q<3; q++) {
Qs.push_back(vector<int>());
Qs.back().push_back(q);
for(int x : list) Qs.back().push_back(x+1);
}
}while(next_permutation(ch, ch+6));
for(int i=0; i<6; i++) ch[i] = (i >= 2) + (i == 5);
do{
vector<int> list; int d = -1;
for(int i=0; i<6; i++) {
if(ch[i] == 1) list.push_back(i);
if(ch[i] == 2) d = i;
}
Qs.push_back(vector<int>());
Qs.back().push_back(3);
for(int x : list) Qs.back().push_back(x+1);
Qs.back().push_back(d+1);
}while(next_permutation(ch, ch+6));
// for(vector<int> cd : Candi) {for(int x : cd) printf("%d ", x); puts("");}
// for(vector<int> &v : Qs) {for(int x : v) printf("%d ", x); puts("");}
vector<int> fs; for(int i=0; i<720; i++) fs.push_back(i);
isCan(6, fs, false);
// if(isCan(6, fs, false)) puts("YES!"); else puts("NO!");
/*
vector<int> all[10];
for(pair<vector<pi>, int> aa : Mp) {
for(pi e : aa.one) printf("[%d %d] ", e.one, e.two); puts("");
printf(": %d\n", aa.two);
all[SZ(aa.one)].push_back(aa.two);
}
for(int i=0; i<6; i++) {
sort(ALL(all[i]));
all[i].erase(unique(ALL(all[i])), all[i].end());
for(int x : all[i]) printf("%d ", x); puts("");
}
*/
}
void orderCoins() {
vector<pi> his;
for(int i=0; i<6; i++) {
int cnt = Mp[his];
vector<int> &v = Qs[cnt];
vector<int> nt[3];
int q = v[0], a = v[1], b = v[2], c = v[3];
int d = -1;
if(q == 3) d = v[4];
int res;
if(q == 0) res = getHeaviest(a, b, c);
if(q == 1) res = getMedian(a, b, c);
if(q == 2) res = getLightest(a, b, c);
if(q == 3) res = getNextLightest(a, b, c, d);
int ix = -1;
for(int k=0; k<3; k++) if(res == v[k+1]) ix = k;
his.push_back(pi(cnt, ix));
}
int ans = Mp[his];
int w[6];
for(int i=0; i<6; i++) w[Candi[ans][i]-1] = i+1;
answer(w);
}
Compilation message
scales.cpp: In function 'bool isCan(int, std::vector<int>, bool)':
scales.cpp:141:13: warning: declaration of 'cnt' shadows a previous local [-Wshadow]
for(int cnt : cntList[6-times]) {
^
scales.cpp:132:9: note: shadowed declaration is here
int cnt = 0;
^
scales.cpp:175:26: warning: unused variable 'res' [-Wunused-variable]
bool res = isCan(times-1, nt[k], true);
^
scales.cpp: At global scope:
scales.cpp:186:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T) {
^
scales.cpp: In function 'void orderCoins()':
scales.cpp:263:32: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
for(int k=0; k<3; k++) if(res == v[k+1]) ix = k;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
2304 KB |
Output is correct |
| 2 |
Correct |
93 ms |
2304 KB |
Output is correct |
| 3 |
Correct |
83 ms |
2304 KB |
Output is correct |
| 4 |
Correct |
79 ms |
2304 KB |
Output is correct |
| 5 |
Correct |
89 ms |
2304 KB |
Output is correct |
| 6 |
Correct |
93 ms |
2304 KB |
Output is correct |
| 7 |
Correct |
69 ms |
2304 KB |
Output is correct |
| 8 |
Correct |
73 ms |
2304 KB |
Output is correct |
| 9 |
Correct |
83 ms |
2304 KB |
Output is correct |
| 10 |
Correct |
79 ms |
2304 KB |
Output is correct |
| 11 |
Correct |
93 ms |
2304 KB |
Output is correct |
| 12 |
Correct |
83 ms |
2304 KB |
Output is correct |
| 13 |
Correct |
79 ms |
2304 KB |
Output is correct |
| 14 |
Correct |
83 ms |
2304 KB |
Output is correct |
| 15 |
Correct |
113 ms |
2304 KB |
Output is correct |
| 16 |
Correct |
83 ms |
2304 KB |
Output is correct |
| 17 |
Correct |
79 ms |
2304 KB |
Output is correct |
| 18 |
Correct |
79 ms |
2304 KB |
Output is correct |
| 19 |
Correct |
93 ms |
2304 KB |
Output is correct |
| 20 |
Correct |
79 ms |
2304 KB |
Output is correct |
| 21 |
Correct |
79 ms |
2304 KB |
Output is correct |
| 22 |
Correct |
86 ms |
2304 KB |
Output is correct |
| 23 |
Correct |
79 ms |
2304 KB |
Output is correct |
| 24 |
Correct |
79 ms |
2304 KB |
Output is correct |
| 25 |
Correct |
83 ms |
2304 KB |
Output is correct |
| 26 |
Correct |
86 ms |
2304 KB |
Output is correct |
| 27 |
Correct |
79 ms |
2304 KB |
Output is correct |
| 28 |
Correct |
73 ms |
2304 KB |
Output is correct |
| 29 |
Correct |
79 ms |
2304 KB |
Output is correct |
| 30 |
Correct |
73 ms |
2304 KB |
Output is correct |
| 31 |
Correct |
73 ms |
2304 KB |
Output is correct |
| 32 |
Correct |
73 ms |
2304 KB |
Output is correct |
| 33 |
Correct |
86 ms |
2304 KB |
Output is correct |
| 34 |
Correct |
73 ms |
2304 KB |
Output is correct |
| 35 |
Correct |
79 ms |
2304 KB |
Output is correct |
| 36 |
Correct |
73 ms |
2304 KB |
Output is correct |
| 37 |
Correct |
73 ms |
2304 KB |
Output is correct |
| 38 |
Correct |
99 ms |
2304 KB |
Output is correct |
| 39 |
Correct |
89 ms |
2304 KB |
Output is correct |
| 40 |
Correct |
83 ms |
2304 KB |
Output is correct |
