Submission #45733

#	Time	Username	Problem	Language	Result	Execution time	Memory
45733		RayaBurong25_1	Scales (IOI15_scales)	C++17	100 / 100	104 ms	892 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

scales

#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); }

Compilation message (stderr)

In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (_ghksjhdfkae19ga_ > 1) 
     ^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  for (i = 0; i < 6; i++) {
  ^~~
scales.cpp: In function 'int answer(int, int, int, int, int, int)':
scales.cpp:21:9: warning: unused variable 'i' [-Wunused-variable]
     int i;
         ^
scales.cpp: In function 'int makeTree(node*, int)':
scales.cpp:92:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                             for (v = 0; v < p->V.size(); v++)
                                         ~~^~~~~~~~~~~~~
scales.cpp:95:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                                 if (Scratch[v].size()*3 > LIM)
                                     ~~~~~~~~~~~~~~~~~~~~^~~~~
scales.cpp:128:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for (v = 0; v < p->V.size(); v++)
                                     ~~^~~~~~~~~~~~~
scales.cpp:134:53: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                             if (Scratch[v].size()*3 > LIM)
                                 ~~~~~~~~~~~~~~~~~~~~^~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:191:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
scales.cpp:204:9: warning: unused variable 'ok' [-Wunused-variable]
     int ok = makeTree(root, 729);
         ^~
scales.cpp:189:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In function 'int answer(int, int, int, int, int, int)':
scales.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask 1100 / 100

#	Verdict	Execution time	Memory	Grader output
Fetching results...