| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 45733 | RayaBurong25_1 | 저울 (IOI15_scales) | C++17 | 104 ms | 892 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scales.h"
#include <vector>
#include <algorithm>
#include <stdio.h>
typedef struct node node;
struct node
{
int q, a, b, c, d;
std::vector<int> V;
node* next[3];
};
node* root;
std::vector<int> Permu[720];
int compare(std::pair<int, int> a, std::pair<int, int> b)
{
return (a.first < b.first);
}
int answer(int P, int q, int a, int b, int c, int d)
{
// printf("answer P%d q%d a%d b%d c%d d%d\n", P, q, a, b, c, d);
int i;
// for (i = 0; i < 6; i++)
// printf("%d ", Permu[P][i]);
// printf("\n");
std::vector<std::pair<int, int> > W;
switch (q)
{
case 1:
W.push_back({Permu[P][a], 0});
W.push_back({Permu[P][b], 1});
W.push_back({Permu[P][c], 2});
std::sort(W.begin(), W.end(), compare);
// printf("%d\n", W[2].second);
return W[2].second;
case 2:
W.push_back({Permu[P][a], 0});
W.push_back({Permu[P][b], 1});
W.push_back({Permu[P][c], 2});
std::sort(W.begin(), W.end(), compare);
// printf("%d\n", W[0].second);
return W[0].second;
break;
case 3:
W.push_back({Permu[P][a], 0});
W.push_back({Permu[P][b], 1});
W.push_back({Permu[P][c], 2});
std::sort(W.begin(), W.end(), compare);
// printf("%d\n", W[1].second);
return W[1].second;
break;
case 4:
if (Permu[P][a] > Permu[P][d]) W.push_back({Permu[P][a], 0});
if (Permu[P][b] > Permu[P][d]) W.push_back({Permu[P][b], 1});
if (Permu[P][c] > Permu[P][d]) W.push_back({Permu[P][c], 2});
std::sort(W.begin(), W.end(), compare);
if (W.size())
{
// printf("%d\n", W[0].second);
return W[0].second;
}
else return answer(P, 2, a, b, c, d);
break;
}
}
int makeTree(node* p, int LIM)
{
// printf("makeTree %p %d %d\n", p, p->V.size(), LIM);
int i, j, k, l, m, v;
// for (i = 0; i < p->V.size(); i++)
// printf("%d ", p->V[i]);
// printf("\n");
if (p->V.size() <= 1)
return 1;
int ok = 0;
std::vector<int> Scratch[3];
for (i = 1; i <= 4; i++)
{
for (j = 0; j < 6; j++)
{
for (k = j + 1; k < 6; k++)
{
for (l = k + 1; l < 6; l++)
{
if (i == 4)
{
for (m = l + 1; m < 6; m++)
{
// printf("i%d j%d k%d l%d m%d\n", i, j, k, l, m);
Scratch[0].clear();
Scratch[1].clear();
Scratch[2].clear();
for (v = 0; v < p->V.size(); v++)
Scratch[answer(p->V[v], i, j, k, l, m)].push_back(p->V[v]);
for (v = 0; v < 3; v++)
if (Scratch[v].size()*3 > LIM)
break;
// printf("%d %d %d\n", Scratch[0].size(), Scratch[1].size(), Scratch[2].size());
if (v == 3)
{
p->q = i;
p->a = j;
p->b = k;
p->c = l;
p->d = m;
if (p->next[0] == NULL) p->next[0] = new node();
p->next[0]->V = Scratch[0];
if (p->next[1] == NULL) p->next[1] = new node();
p->next[1]->V = Scratch[1];
if (p->next[2] == NULL) p->next[2] = new node();
p->next[2]->V = Scratch[2];
// printf("%p %d %d %d %d %d = %d %d %d\n", p, i, j, k, l, m, Scratch[0].size(), Scratch[1].size(), Scratch[2].size());
ok = 1;
ok &= makeTree(p->next[0], LIM/3);
ok &= makeTree(p->next[1], LIM/3);
ok &= makeTree(p->next[2], LIM/3);
// ok = 1;
if (ok)
break;
}
}
}
else
{
// printf("i%d j%d k%d l%d\n", i, j, k, l);
Scratch[0].clear();
Scratch[1].clear();
Scratch[2].clear();
for (v = 0; v < p->V.size(); v++)
{
// printf("%d\n", answer(p->V[v], i, j, k, l, m));
Scratch[answer(p->V[v], i, j, k, l, m)].push_back(p->V[v]);
}
for (v = 0; v < 3; v++)
if (Scratch[v].size()*3 > LIM)
break;
if (v == 3)
{
p->q = i;
p->a = j;
p->b = k;
p->c = l;
p->d = m;
if (p->next[0] == NULL) p->next[0] = new node();
p->next[0]->V = Scratch[0];
if (p->next[1] == NULL) p->next[1] = new node();
p->next[1]->V = Scratch[1];
if (p->next[2] == NULL) p->next[2] = new node();
p->next[2]->V = Scratch[2];
// printf("%p %d %d %d %d %d = %d %d %d\n", p, i, j, k, l, m, Scratch[0].size(), Scratch[1].size(), Scratch[2].size());
ok = 1;
ok &= makeTree(p->next[0], LIM/3);
ok &= makeTree(p->next[1], LIM/3);
ok &= makeTree(p->next[2], LIM/3);
// ok = 1;
if (ok)
break;
}
}
if (ok) break;
}
if (ok) break;
}
if (ok) break;
}
if (ok) break;
}
// printf("ok %d\n", ok);
// p->q = i;
// p->a = j;
// p->b = k;
// p->c = l;
// p->d = m;
// p->next[0] = new node();
// p->next[0]->V = Scratch[0];
// p->next[1] = new node();
// p->next[1]->V = Scratch[1];
// p->next[2] = new node();
// p->next[2]->V = Scratch[2];
// printf("%p %d %d %d %d %d = %d %d %d\n", p, i, j, k, l, m, Scratch[0].size(), Scratch[1].size(), Scratch[2].size());
// makeTree(p->next[0]);
// makeTree(p->next[1]);
// makeTree(p->next[2]);
return ok;
}
void init(int T) {
root = new node();
int i, j;
for (i = 0; i < 720; i++)
root->V.push_back(i);
for (i = 0; i < 6; i++)
Permu[0].push_back(i);
for (i = 1; i < 720; i++)
{
Permu[i] = Permu[i - 1];
std::next_permutation(Permu[i].begin(), Permu[i].end());
// for (j = 0; j < 6; j++)
// printf("%d ", Permu[i][j]);
// printf("\n");
}
int ok = makeTree(root, 729);
// printf("ok %d\n", ok);
}
void orderCoins() {
node* p = root;
int i, r;
while (p->V.size() > 1)
{
// printf("q %d a %d b %d c %d d %d\n", p->q, p->a, p->b, p->c, p->d);
switch (p->q)
{
case 1:
r = getHeaviest(p->a + 1, p->b + 1, p->c + 1);
if (r == p->a + 1) p = p->next[0];
else if (r == p->b + 1) p = p->next[1];
else if (r == p->c + 1) p = p->next[2];
break;
case 2:
r = getLightest(p->a + 1, p->b + 1, p->c + 1);
if (r == p->a + 1) p = p->next[0];
else if (r == p->b + 1) p = p->next[1];
else if (r == p->c + 1) p = p->next[2];
break;
case 3:
r = getMedian(p->a + 1, p->b + 1, p->c + 1);
if (r == p->a + 1) p = p->next[0];
else if (r == p->b + 1) p = p->next[1];
else if (r == p->c + 1) p = p->next[2];
break;
case 4:
r = getNextLightest(p->a + 1, p->b + 1, p->c + 1, p->d + 1);
if (r == p->a + 1) p = p->next[0];
else if (r == p->b + 1) p = p->next[1];
else if (r == p->c + 1) p = p->next[2];
break;
}
// printf("r %d\n", r);
}
int W[6];
for (i = 0; i < 6; i++)
{
W[Permu[p->V[0]][i]] = i + 1;
}
// for (i = 0; i < 6; i++)
// {
// printf("W %d\n", W[i]);
// }
answer(W);
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||