| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 130568 | keko37 | 저울 (IOI15_scales) | C++14 | 10 ms | 512 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}*/
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||