Submission #45729

# Submission time Handle Problem Language Result Execution time Memory
45729 2018-04-16T04:58:06 Z RayaBurong25_1 Scales (IOI15_scales) C++17
0 / 100
112 ms 1476 KB
#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];
            if (r == p->b + 1) p = p->next[1];
            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];
            if (r == p->b + 1) p = p->next[1];
            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];
            if (r == p->b + 1) p = p->next[1];
            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];
            if (r == p->b + 1) p = p->next[1];
            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

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]
 }
 ^
# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 55 ms 888 KB Output isn't correct
3 Incorrect 58 ms 888 KB Output isn't correct
4 Incorrect 56 ms 916 KB Output isn't correct
5 Runtime error 106 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 60 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 58 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 62 ms 1144 KB Output isn't correct
9 Runtime error 75 ms 1244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 58 ms 1304 KB Output isn't correct
11 Incorrect 81 ms 1304 KB Output isn't correct
12 Incorrect 58 ms 1304 KB Output isn't correct
13 Runtime error 57 ms 1304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 67 ms 1304 KB Output isn't correct
15 Incorrect 58 ms 1304 KB Output isn't correct
16 Incorrect 58 ms 1304 KB Output isn't correct
17 Incorrect 61 ms 1304 KB Output isn't correct
18 Runtime error 56 ms 1304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Incorrect 59 ms 1304 KB Output isn't correct
20 Incorrect 58 ms 1304 KB Output isn't correct
21 Incorrect 55 ms 1304 KB Output isn't correct
22 Runtime error 56 ms 1304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Incorrect 61 ms 1432 KB Output isn't correct
24 Incorrect 55 ms 1432 KB Output isn't correct
25 Incorrect 62 ms 1432 KB Output isn't correct
26 Runtime error 55 ms 1432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 56 ms 1432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Incorrect 56 ms 1432 KB Output isn't correct
29 Runtime error 56 ms 1432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Incorrect 61 ms 1476 KB Output isn't correct
31 Incorrect 73 ms 1476 KB Output isn't correct
32 Incorrect 56 ms 1476 KB Output isn't correct
33 Incorrect 97 ms 1476 KB Output isn't correct
34 Runtime error 112 ms 1476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 55 ms 1476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 58 ms 1476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Incorrect 57 ms 1476 KB Output isn't correct
38 Runtime error 57 ms 1476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 62 ms 1476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 60 ms 1476 KB Execution killed with signal 11 (could be triggered by violating memory limits)