#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
const int MAXN = 5005;
int cnt, kreni;
int sus[3][MAXN];
int p[750][7], pos[750][7];
int sol[MAXN], tip[MAXN], aa[MAXN], bb[MAXN], cc[MAXN], dd[MAXN];
void indeksiraj () {
int c[6] = {0, 1, 2, 3, 4, 5};
int cnt = 0;
do {
for (int i=0; i<6; i++) {
p[cnt][i] = c[i];
pos[cnt][p[cnt][i]] = i;
}
cnt++;
} while (next_permutation(c, c + 6));
}
vector <int> va, vb, vc;
bool partMin (const vector <int> &v, int a, int b, int c, int siz) {
va.clear(); vb.clear(); vc.clear();
int lim = v.size(), x, y, z;
for (int i=0; i<lim; i++) {
x = pos[v[i]][a];
y = pos[v[i]][b];
z = pos[v[i]][c];
if (x < y && x < z) va.push_back(v[i]);
if (y < x && y < z) vb.push_back(v[i]);
if (z < x && z < y) vc.push_back(v[i]);
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
}
return 1;
}
bool partMax (const vector <int> &v, int a, int b, int c, int siz) {
va.clear(); vb.clear(); vc.clear();
int lim = v.size(), x, y, z;
for (int i=0; i<lim; i++) {
x = pos[v[i]][a];
y = pos[v[i]][b];
z = pos[v[i]][c];
if (x > y && x > z) va.push_back(v[i]);
if (y > x && y > z) vb.push_back(v[i]);
if (z > x && z > y) vc.push_back(v[i]);
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
}
return 1;
}
bool partMed (const vector <int> &v, int a, int b, int c, int siz) {
va.clear(); vb.clear(); vc.clear();
int lim = v.size(), x, y, z;
for (int i=0; i<lim; i++) {
x = pos[v[i]][a];
y = pos[v[i]][b];
z = pos[v[i]][c];
if (y < x && x < z || z < x && x < y) va.push_back(v[i]);
if (x < y && y < z || z < y && y < x) vb.push_back(v[i]);
if (x < z && z < y || y < z && z < x) vc.push_back(v[i]);
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
}
return 1;
}
bool partMagic (const vector <int> &v, int a, int b, int c, int d, int siz) {
va.clear(); vb.clear(); vc.clear();
int lim = v.size(), x, y, z, w;
for (int i=0; i<lim; i++) {
x = pos[v[i]][a];
y = pos[v[i]][b];
z = pos[v[i]][c];
w = pos[v[i]][d];
if (x < y && y < z) {
if (w < x) va.push_back(v[i]);
else if (w < y) vb.push_back(v[i]);
else if (w < z) vc.push_back(v[i]);
else va.push_back(v[i]);
} else if (x < z && z < y) {
if (w < x) va.push_back(v[i]);
else if (w < z) vc.push_back(v[i]);
else if (w < y) vb.push_back(v[i]);
else va.push_back(v[i]);
} else if (y < x && x < z) {
if (w < y) vb.push_back(v[i]);
else if (w < x) va.push_back(v[i]);
else if (w < z) vc.push_back(v[i]);
else vb.push_back(v[i]);
} else if (y < z && z < x) {
if (w < y) vb.push_back(v[i]);
else if (w < z) vc.push_back(v[i]);
else if (w < x) va.push_back(v[i]);
else vb.push_back(v[i]);
} else if (z < x && x < y) {
if (w < z) vc.push_back(v[i]);
else if (w < x) va.push_back(v[i]);
else if (w < y) vb.push_back(v[i]);
else vc.push_back(v[i]);
} else if (z < y && y < x) {
if (w < z) vc.push_back(v[i]);
else if (w < y) vb.push_back(v[i]);
else if (w < x) va.push_back(v[i]);
else vc.push_back(v[i]);
}
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
}
return 1;
}
bool ima (vector <int> v, int x) {
for (auto e : v) if (e == x) return 1; return 0;
}
int nadi (vector <int> v, int siz, int dub) {
if (v.size() <= 1) {
cnt++;
//if (cnt == 1668) cout << "sad je " << v[0] << endl;
if (!v.empty()) sol[cnt] = v[0] + 1;
return cnt;
}
for (int a=0; a<6; a++) {
for (int b=a+1; b<6; b++) {
for (int c=b+1; c<6; c++) {
if (partMin(v, a, b, c, siz/3)) {
vector <int> vva = va, vvb = vb, vvc = vc;
int sa, sb, sc, flg = 0;
if (flg == 0) {sa = nadi(vva, siz/3, dub + 1); if (sa == 0) flg = 1;}
if (flg == 0) {sb = nadi(vvb, siz/3, dub + 1); if (sb == 0) flg = 1;}
if (flg == 0) {sc = nadi(vvc, siz/3, dub + 1); if (sc == 0) flg = 1;}
if (flg == 0) {
cnt++;
tip[cnt] = 1; aa[cnt] = a; bb[cnt] = b; cc[cnt] = c;
sus[0][cnt] = sa; sus[1][cnt] = sb; sus[2][cnt] = sc;
return cnt;
}
}
if (partMax(v, a, b, c, siz/3)) {
vector <int> vva = va, vvb = vb, vvc = vc;
int sa, sb, sc, flg = 0;
if (flg == 0) {sa = nadi(vva, siz/3, dub + 1); if (sa == 0) flg = 1;}
if (flg == 0) {sb = nadi(vvb, siz/3, dub + 1); if (sb == 0) flg = 1;}
if (flg == 0) {sc = nadi(vvc, siz/3, dub + 1); if (sc == 0) flg = 1;}
if (flg == 0) {
cnt++;
tip[cnt] = 2; aa[cnt] = a; bb[cnt] = b; cc[cnt] = c;
sus[0][cnt] = sa; sus[1][cnt] = sb; sus[2][cnt] = sc;
return cnt;
}
}
if (partMed(v, a, b, c, siz/3)) {
vector <int> vva = va, vvb = vb, vvc = vc;
int sa, sb, sc, flg = 0;
if (flg == 0) {sa = nadi(vva, siz/3, dub + 1); if (sa == 0) flg = 1;}
if (flg == 0) {sb = nadi(vvb, siz/3, dub + 1); if (sb == 0) flg = 1;}
if (flg == 0) {sc = nadi(vvc, siz/3, dub + 1); if (sc == 0) flg = 1;}
if (flg == 0) {
cnt++;
//if (cnt == 1670) cout << "bla " << vva[0] << " " << vvb[0] << " " << vvc[0] << " " << ima(v, 719) << endl;
tip[cnt] = 3; aa[cnt] = a; bb[cnt] = b; cc[cnt] = c;
sus[0][cnt] = sa; sus[1][cnt] = sb; sus[2][cnt] = sc;
return cnt;
}
}
for (int d = 0; d < 6; d++) {
if (d == a || d == b || d == c) continue;
if (partMagic(v, a, b, c, d, siz/3)) {
vector <int> vva = va, vvb = vb, vvc = vc;
int sa, sb, sc, flg = 0;
if (flg == 0) {sa = nadi(vva, siz/3, dub + 1); if (sa == 0) flg = 1;}
if (flg == 0) {sb = nadi(vvb, siz/3, dub + 1); if (sb == 0) flg = 1;}
if (flg == 0) {sc = nadi(vvc, siz/3, dub + 1); if (sc == 0) flg = 1;}
if (flg == 0) {
cnt++;
tip[cnt] = 4; aa[cnt] = a; bb[cnt] = b; cc[cnt] = c; dd[cnt] = d;
sus[0][cnt] = sa; sus[1][cnt] = sb; sus[2][cnt] = sc;
return cnt;
}
}
}
}
}
}
return 0;
}
void init (int T) {
indeksiraj();
vector <int> v;
for (int i=0; i<720; i++) v.push_back(i);
kreni = nadi(v, 729, 0);
}
/*
void answer(int A[]) {}
int getLightest (int a, int b, int c) {cout << "L " << a << " " << b << " " << c << endl; int res; cin >> res; return res;}
int getHeaviest (int a, int b, int c) {cout << "H " << a << " " << b << " " << c << endl; int res; cin >> res; return res;}
int getMedian (int a, int b, int c) {cout << "M " << a << " " << b << " " << c << endl; int res; cin >> res; return res;}
int getNextLightest (int a, int b, int c, int d) {cout << "NL " << a << " " << b << " " << c << " " << d << endl; int res; cin >> res; return res;}
*/
int rjesi (int curr) {
if (sol[curr] != 0) return sol[curr] - 1;
int a = aa[curr] + 1, b = bb[curr] + 1, c = cc[curr] + 1, d = dd[curr] + 1;
int res;
if (tip[curr] == 1) res = getLightest(a, b, c);
if (tip[curr] == 2) res = getHeaviest(a, b, c);
if (tip[curr] == 3) res = getMedian(a, b, c);
if (tip[curr] == 4) res = getNextLightest(a, b, c, d);
if (res == a) return rjesi(sus[0][curr]);
if (res == b) return rjesi(sus[1][curr]);
if (res == c) return rjesi(sus[2][curr]);
}
void orderCoins() {
int ind = rjesi(kreni);
//for (int i=0; i<6; i++) cout << p[ind][i] + 1 << " "; cout << endl;
int A[] = {p[ind][0] + 1, p[ind][1] + 1, p[ind][2] + 1, p[ind][3] + 1, p[ind][4] + 1, p[ind][5] + 1};
answer(A);
}
/*int main () {
init(1);
for (int i=0; i<5; i++) {
orderCoins();
}
return 0;
}*/
Compilation message
scales.cpp: In function 'void indeksiraj()':
scales.cpp:15:9: warning: declaration of 'cnt' shadows a global declaration [-Wshadow]
int cnt = 0;
^~~
scales.cpp:8:5: note: shadowed declaration is here
int cnt, kreni;
^~~
scales.cpp: In function 'bool partMin(const std::vector<int>&, int, int, int, int)':
scales.cpp:29:21: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int lim = v.size(), x, y, z;
~~~~~~^~
scales.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
~~~~~~~~~~^~~~~
scales.cpp:37:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
~~~~~~~~~~^~~~~
scales.cpp:37:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
~~~~~~~~~~^~~~~
scales.cpp: In function 'bool partMax(const std::vector<int>&, int, int, int, int)':
scales.cpp:44:21: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int lim = v.size(), x, y, z;
~~~~~~^~
scales.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
~~~~~~~~~~^~~~~
scales.cpp:52:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
~~~~~~~~~~^~~~~
scales.cpp:52:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
~~~~~~~~~~^~~~~
scales.cpp: In function 'bool partMed(const std::vector<int>&, int, int, int, int)':
scales.cpp:59:21: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int lim = v.size(), x, y, z;
~~~~~~^~
scales.cpp:64:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (y < x && x < z || z < x && x < y) va.push_back(v[i]);
~~~~~~^~~~~~~~
scales.cpp:65:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (x < y && y < z || z < y && y < x) vb.push_back(v[i]);
~~~~~~^~~~~~~~
scales.cpp:66:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (x < z && z < y || y < z && z < x) vc.push_back(v[i]);
~~~~~~^~~~~~~~
scales.cpp:67:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
~~~~~~~~~~^~~~~
scales.cpp:67:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
~~~~~~~~~~^~~~~
scales.cpp:67:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
~~~~~~~~~~^~~~~
scales.cpp: In function 'bool partMagic(const std::vector<int>&, int, int, int, int, int)':
scales.cpp:74:21: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int lim = v.size(), x, y, z, w;
~~~~~~^~
scales.cpp:111:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
~~~~~~~~~~^~~~~
scales.cpp:111:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
~~~~~~~~~~^~~~~
scales.cpp:111:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
~~~~~~~~~~^~~~~
scales.cpp: In function 'bool ima(std::vector<int>, int)':
scales.cpp:117:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (auto e : v) if (e == x) return 1; return 0;
^~~
scales.cpp:117:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (auto e : v) if (e == x) return 1; return 0;
^~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:192:16: warning: unused parameter 'T' [-Wunused-parameter]
void init (int T) {
^
scales.cpp: In function 'int rjesi(int)':
scales.cpp:218:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
scales.cpp:217:5: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
if (res == c) return rjesi(sus[2][curr]);
^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
504 KB |
Output is correct |
2 |
Correct |
10 ms |
504 KB |
Output is correct |
3 |
Correct |
10 ms |
504 KB |
Output is correct |
4 |
Correct |
10 ms |
504 KB |
Output is correct |
5 |
Correct |
10 ms |
504 KB |
Output is correct |
6 |
Correct |
10 ms |
504 KB |
Output is correct |
7 |
Correct |
10 ms |
504 KB |
Output is correct |
8 |
Correct |
10 ms |
504 KB |
Output is correct |
9 |
Correct |
9 ms |
504 KB |
Output is correct |
10 |
Correct |
9 ms |
504 KB |
Output is correct |
11 |
Correct |
10 ms |
504 KB |
Output is correct |
12 |
Correct |
9 ms |
504 KB |
Output is correct |
13 |
Correct |
10 ms |
504 KB |
Output is correct |
14 |
Correct |
10 ms |
512 KB |
Output is correct |
15 |
Correct |
10 ms |
504 KB |
Output is correct |
16 |
Correct |
10 ms |
504 KB |
Output is correct |
17 |
Correct |
10 ms |
504 KB |
Output is correct |
18 |
Correct |
10 ms |
504 KB |
Output is correct |
19 |
Correct |
10 ms |
504 KB |
Output is correct |
20 |
Correct |
10 ms |
504 KB |
Output is correct |
21 |
Correct |
10 ms |
504 KB |
Output is correct |
22 |
Correct |
10 ms |
504 KB |
Output is correct |
23 |
Correct |
10 ms |
488 KB |
Output is correct |
24 |
Correct |
10 ms |
504 KB |
Output is correct |
25 |
Correct |
10 ms |
504 KB |
Output is correct |
26 |
Correct |
10 ms |
504 KB |
Output is correct |
27 |
Correct |
10 ms |
504 KB |
Output is correct |
28 |
Correct |
10 ms |
504 KB |
Output is correct |
29 |
Correct |
10 ms |
504 KB |
Output is correct |
30 |
Correct |
10 ms |
504 KB |
Output is correct |
31 |
Correct |
10 ms |
508 KB |
Output is correct |
32 |
Correct |
9 ms |
504 KB |
Output is correct |
33 |
Correct |
9 ms |
504 KB |
Output is correct |
34 |
Correct |
10 ms |
508 KB |
Output is correct |
35 |
Correct |
10 ms |
504 KB |
Output is correct |
36 |
Correct |
10 ms |
504 KB |
Output is correct |
37 |
Correct |
9 ms |
504 KB |
Output is correct |
38 |
Correct |
9 ms |
504 KB |
Output is correct |
39 |
Correct |
10 ms |
504 KB |
Output is correct |
40 |
Correct |
10 ms |
504 KB |
Output is correct |