oj.uz

Submission #249745

# Submission time Handle Problem Language Result Execution time Memory
249745 2020-07-15T16:35:35 Z stoyan_malinin Mechanical Doll (IOI18_doll) C++14
100 / 100
 378 ms 74216 KB 
#include "doll.h"
//#include "grader.cpp"

#include <iostream>
#include <map>
#include <set>

using namespace std;

const int MAXN = 5e5 + 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];
bool removed[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, useless;
    vector <RouterOutput> outs;

    int removedCnt = 0;

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

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

        optimize(root);
        initOuts();
    }

    void optimize(int sInd)
    {
        //cout << sInd << " -> " << s[sInd].out[0] << '\n';
        if(s[sInd].out[0]==MAXN)
        {
            if(useless>=2)
            {
                useless -= 2;
                removed[sInd] = 1;

                //cout << "remove*: " << sInd << '\n';

                removedCnt++;
            }
            return;
        }

        optimize(-s[sInd].out[0]);
        optimize(-s[sInd].out[1]);

        if(removed[ -s[sInd].out[0] ]==true && removed[ -s[sInd].out[1] ]==true)
        {
            //cout << "remove: " << sInd << '\n';

            removed[sInd] = 1;
            removedCnt++;
        }
        else if(removed[ -s[sInd].out[0] ]==true)
        {
            s[sInd].out[0] = -root;
        }
        else if(removed[ -s[sInd].out[1] ]==true)
        {
            s[sInd].out[1] = -root;
        }
    }

    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[1], (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 relabel(vector <int> &c, vector <int> &x, vector <int> &y)
{
    set <int> s;
    for(int i = 1;i<=usedSwitches;i++)
    {
        if(removed[i]==false) s.insert(i);
    }

    map <int, int> mp;

    //cout << x.size() << '\n';
    //for(int i = 0;i<x.size();i++) cout << x[i] << " " << y[i] << '\n';

    //cout << '\n' << '\n';

    int ind = 0;
    for(int a: s)
    {
        ind++;
        mp[-a] = -ind;

        //cout << a << " vs " << ind << '\n';

        swap(x[a-1], x[ind-1]);
        swap(y[a-1], y[ind-1]);
    }

    for(int &b: c)
    {
        if(b<0) b = mp[b];
    }
    for(int &b: x)
    {
        if(b<0) b = mp[b];
    }
    for(int &b: y)
    {
        if(b<0) b = mp[b];
    }

    while(x.size()!=ind) x.pop_back(), y.pop_back();

    //cout << x.size() << '\n';
    //for(int i = 0;i<x.size();i++) cout << x[i] << " " << y[i] << '\n';
}

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

    if(A.size()==1)
    {
        C[0] = A[0];
        C[ A[0] ] = 0;

        answer(C, {}, {});
        return;
    }

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

    int sz = 1;
    while(sz<A.size()-1) sz *= 2;

    Router R = Router(sz, sz-(A.size()-1));

    C[0] = A[0];
    for(int i = 1;i<=M;i++) C[i] = -1;

    int useLess = R.useless;
    for(int i = 0;i<useLess;i++) R.outs[i].assignDirection(-R.root);

    for(int i = 0;i<A.size()-1;i++)
    {
        R.outs[useLess+i].assignDirection(A[i+1]);
    }

    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';
    }
    relabel(C, X, Y);

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

4 7
1 3 4 2 1 2 2

1 12
1 1 1 1 1 1 1 1 1 1 1 1

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

5 4
1 1 1 1
*/

Compilation message

doll.cpp: In function 'void relabel(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
doll.cpp:203:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  203 |     while(x.size()!=ind) x.pop_back(), y.pop_back();
      |           ~~~~~~~~^~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:223:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |     for(int i = 0;i<A.size()-1;i++) nxt[ A[i] ].push_back(A[i+1]);
      |                   ~^~~~~~~~~~~
doll.cpp:226:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |     while(sz<A.size()-1) sz *= 2;
      |           ~~^~~~~~~~~~~
doll.cpp:236:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |     for(int i = 0;i<A.size()-1;i++)
      |                   ~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 43284 KB Output is correct
2 Correct 129 ms 53592 KB Output is correct
3 Correct 145 ms 57444 KB Output is correct
4 Correct 37 ms 43332 KB Output is correct
5 Correct 61 ms 44504 KB Output is correct
6 Correct 220 ms 60696 KB Output is correct
7 Correct 36 ms 43284 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 43284 KB Output is correct
2 Correct 129 ms 53592 KB Output is correct
3 Correct 145 ms 57444 KB Output is correct
4 Correct 37 ms 43332 KB Output is correct
5 Correct 61 ms 44504 KB Output is correct
6 Correct 220 ms 60696 KB Output is correct
7 Correct 36 ms 43284 KB Output is correct
8 Correct 224 ms 60940 KB Output is correct
9 Correct 309 ms 70196 KB Output is correct
10 Correct 361 ms 74216 KB Output is correct
11 Correct 29 ms 43332 KB Output is correct
12 Correct 32 ms 43352 KB Output is correct
13 Correct 28 ms 43300 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 43284 KB Output is correct
2 Correct 129 ms 53592 KB Output is correct
3 Correct 145 ms 57444 KB Output is correct
4 Correct 37 ms 43332 KB Output is correct
5 Correct 61 ms 44504 KB Output is correct
6 Correct 220 ms 60696 KB Output is correct
7 Correct 36 ms 43284 KB Output is correct
8 Correct 224 ms 60940 KB Output is correct
9 Correct 309 ms 70196 KB Output is correct
10 Correct 361 ms 74216 KB Output is correct
11 Correct 29 ms 43332 KB Output is correct
12 Correct 32 ms 43352 KB Output is correct
13 Correct 28 ms 43300 KB Output is correct
14 Correct 359 ms 73024 KB Output is correct
15 Correct 303 ms 68152 KB Output is correct
16 Correct 378 ms 72440 KB Output is correct
17 Correct 34 ms 43340 KB Output is correct
18 Correct 32 ms 43340 KB Output is correct
19 Correct 27 ms 43340 KB Output is correct
20 Correct 353 ms 73472 KB Output is correct
21 Correct 33 ms 43332 KB Output is correct
22 Correct 36 ms 43304 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 43356 KB Output is correct
2 Correct 28 ms 43352 KB Output is correct
3 Correct 30 ms 43340 KB Output is correct
4 Correct 28 ms 43248 KB Output is correct
5 Correct 36 ms 43288 KB Output is correct
6 Correct 30 ms 43356 KB Output is correct
7 Correct 25 ms 43360 KB Output is correct
8 Correct 28 ms 43328 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 43288 KB Output is correct
2 Correct 181 ms 59236 KB Output is correct
3 Correct 254 ms 67596 KB Output is correct
4 Correct 307 ms 71512 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 43288 KB Output is correct
2 Correct 181 ms 59236 KB Output is correct
3 Correct 254 ms 67596 KB Output is correct
4 Correct 307 ms 71512 KB Output is correct
5 Correct 359 ms 73136 KB Output is correct
6 Correct 326 ms 72632 KB Output is correct
7 Correct 342 ms 72812 KB Output is correct
8 Correct 323 ms 72464 KB Output is correct
9 Correct 248 ms 67588 KB Output is correct
10 Correct 323 ms 71884 KB Output is correct
11 Correct 313 ms 72280 KB Output is correct
12 Correct 254 ms 68028 KB Output is correct
13 Correct 196 ms 59924 KB Output is correct
14 Correct 267 ms 68384 KB Output is correct
15 Correct 263 ms 68500 KB Output is correct
16 Correct 34 ms 44144 KB Output is correct
17 Correct 182 ms 59644 KB Output is correct
18 Correct 181 ms 59460 KB Output is correct
19 Correct 273 ms 68008 KB Output is correct
20 Correct 350 ms 71856 KB Output is correct
21 Correct 314 ms 72156 KB Output is correct
22 Correct 321 ms 71728 KB Output is correct