oj.uz

Submission #249705

# Submission time Handle Problem Language Result Execution time Memory
249705 2020-07-15T15:04:39 Z stoyan_malinin Mechanical Doll (IOI18_doll) C++14
16 / 100
 127 ms 28944 KB 
#include "doll.h"
//#include "grader.cpp"

#include <iostream>

using namespace std;

const int MAXN = 2e5 + 5;

int usedSwitches = 0;

struct Switch
{
    static int switchCnt;

    int num;
    int state;

    int out[2];

    Switch()
    {
        this->num = switchCnt;
        switchCnt++;

        this->state = 0;
        this->out[0] = this->out[1] = MAXN;
    }
};
int Switch::switchCnt = 0;

Switch s[MAXN];

struct RouterOutput
{
    int switchNum, outNum;

    RouterOutput(){}
    RouterOutput(int switchNum, int outNum)
    {
        this->outNum = outNum;
        this->switchNum = switchNum;
    }

    void assignDirection(int nxt)
    {
        s[switchNum].out[outNum] = nxt;
    }
};

struct Router
{
    int root, sz;
    vector <RouterOutput> outs;

    Router(){}
    Router(int sz)
    {
        usedSwitches++;
        this->root = usedSwitches;

        this->sz = sz;
        build(root, 0, sz-1);

        initOuts();
    }

    void build(int sInd, int l, int r)
    {
        //cout << sInd << " || " << l << " " << r << '\n';

        if(l+1==r) return;
        if(l+2==r)
        {
            usedSwitches++;
            s[sInd].out[0] = -usedSwitches;

            return;
        }

        usedSwitches++;
        s[sInd].out[0] = -usedSwitches;

        usedSwitches++;
        s[sInd].out[1] = -usedSwitches;

        build(s[sInd].out[0], l, (l+r)/2);
        build(s[sInd].out[0], (l+r)/2+1, r);
    }

    void initOuts()
    {
        for(int i = 0;i<sz;i++)
        {
            int sInd = root;
            while(true)
            {
                if(s[sInd].out[ s[sInd].state ]==MAXN)
                {
                    outs.push_back(RouterOutput(sInd, s[sInd].state));
                    s[sInd].state ^= 1;

                    break;
                }

                s[sInd].state ^= 1;
                sInd = -s[sInd].out[ s[sInd].state^1 ];
            }
        }

        if(outs.size()!=sz) answer({}, {}, {});
        //for(RouterOutput x: outs) cout << x.switchNum << " " << x.outNum << '\n';
    }
};

Router r[MAXN];
vector <int> nxt[MAXN];



void create_circuit(int M, vector <int> A)
{
    vector <int> C(M+1);

    A.push_back(0);
    for(int i = 0;i<A.size()-1;i++) nxt[ A[i] ].push_back(A[i+1]);

    C[0] = A[0];
    for(int i = 1;i<=M;i++)
    {
        if(nxt[i].size()>1)
        {
            int sz = 1;
            while(sz<nxt[i].size()) sz *= 2;

            r[i] = Router(sz);
            C[i] = -r[i].root;
        }
        else
        {
            if(nxt[i].size()==1) C[i] = nxt[i][0];
            else C[i] = 0;
        }
    }

    for(int x = 1;x<=M;x++)
    {
        if(nxt[x].size()<=1) continue;

        int useLess = r[x].sz - nxt[x].size();
        for(int i = 0;i<useLess;i++) r[x].outs[i].assignDirection(-r[x].root);

        for(int i = 0;i<nxt[x].size();i++)
        {
            r[x].outs[useLess+i].assignDirection(nxt[x][i]);
        }
    }

    //cout << '\n';

    //for(int i = 0;i<=M;i++) cout << C[i] << '\n';

    vector <int> X(usedSwitches), Y(usedSwitches);
    for(int i = 1;i<=usedSwitches;i++)
    {
        X[i-1] = s[i].out[0];
        Y[i-1] = s[i].out[1];

        //cout << X[i-1] << " " << Y[i-1] << '\n';
    }

    answer(C, X, Y);
}
/*
4 4
1 2 1 3

4 7
1 3 4 2 1 2 2

5 11
1 2 5 2 3 4 1 2 5 5 4

5 4
1 1 1 1
*/

Compilation message

doll.cpp: In member function 'void Router::initOuts()':
doll.cpp:111:23: warning: comparison of integer expressions of different signedness: 'std::vector<RouterOutput>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |         if(outs.size()!=sz) answer({}, {}, {});
      |            ~~~~~~~~~~~^~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:126:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for(int i = 0;i<A.size()-1;i++) nxt[ A[i] ].push_back(A[i+1]);
      |                   ~^~~~~~~~~~~
doll.cpp:134:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             while(sz<nxt[i].size()) sz *= 2;
      |                   ~~^~~~~~~~~~~~~~
doll.cpp:153:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |         for(int i = 0;i<nxt[x].size();i++)
      |                       ~^~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14284 KB Output is correct
2 Correct 46 ms 18080 KB Output is correct
3 Correct 44 ms 17600 KB Output is correct
4 Correct 11 ms 14284 KB Output is correct
5 Correct 21 ms 15528 KB Output is correct
6 Correct 85 ms 19444 KB Output is correct
7 Correct 11 ms 14284 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14284 KB Output is correct
2 Correct 46 ms 18080 KB Output is correct
3 Correct 44 ms 17600 KB Output is correct
4 Correct 11 ms 14284 KB Output is correct
5 Correct 21 ms 15528 KB Output is correct
6 Correct 85 ms 19444 KB Output is correct
7 Correct 11 ms 14284 KB Output is correct
8 Correct 70 ms 22212 KB Output is correct
9 Correct 73 ms 21800 KB Output is correct
10 Correct 123 ms 26328 KB Output is correct
11 Correct 12 ms 14284 KB Output is correct
12 Correct 11 ms 14284 KB Output is correct
13 Correct 9 ms 14384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14284 KB Output is correct
2 Correct 46 ms 18080 KB Output is correct
3 Correct 44 ms 17600 KB Output is correct
4 Correct 11 ms 14284 KB Output is correct
5 Correct 21 ms 15528 KB Output is correct
6 Correct 85 ms 19444 KB Output is correct
7 Correct 11 ms 14284 KB Output is correct
8 Correct 70 ms 22212 KB Output is correct
9 Correct 73 ms 21800 KB Output is correct
10 Correct 123 ms 26328 KB Output is correct
11 Correct 12 ms 14284 KB Output is correct
12 Correct 11 ms 14284 KB Output is correct
13 Correct 9 ms 14384 KB Output is correct
14 Correct 127 ms 28644 KB Output is correct
15 Correct 68 ms 21432 KB Output is correct
16 Correct 108 ms 25180 KB Output is correct
17 Correct 11 ms 14284 KB Output is correct
18 Correct 11 ms 14284 KB Output is correct
19 Correct 10 ms 14340 KB Output is correct
20 Correct 113 ms 27040 KB Output is correct
21 Correct 10 ms 14300 KB Output is correct
22 Correct 11 ms 14352 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 28912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 28944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 28944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -