oj.uz

Submission #427438

# Submission time Handle Problem Language Result Execution time Memory
427438 2021-06-14T15:15:07 Z Aldas25 Mechanical Doll (IOI18_doll) C++14
53 / 100
 305 ms 51464 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;

const int INF = 1e9;

void create_circuit(int m, vi a) {
    int n = a.size();
    a.pb(0);
    vi C(m + 1);
    C[0] = a[0];
    for (int i = 1; i <= m; ++i) {
        C[i] = 0;
    }

    vector<vi> tmp(m+1);
    FOR(i, 0, n-1) {
        tmp[a[i]].pb(a[i+1]);
    }
    vector<vi> out;
    vi pr;
    vi X, Y;
//cout << " hh" << endl;
    FOR(i, 1, m) {
  //      cout << " i = " << i << endl;
        vi cur;
        cur.pb(i);
    //    cout << " asdaasdasd s " << endl;
        for (int xx : tmp[i]) {
      //      cout << "    pushing xx = " << xx << endl;
            cur.pb(xx);
        //    cout << "   after pu" << endl;
        }
       // cout <<"  asdffsfsdfsdfsdfds" << endl;
        out.pb(cur);
    }
//cout << " asdas" << endl;
    FOR(i, 0, (int)out.size()-1) {
  //      cout << " i=" << i << endl;
        vi cur = out[i];
        out[i].clear();
        //cout << " cur: ";
        //for (int xx : cur) cout << xx << " ";
        //cout << endl;

        int id = cur[0];
        if ((int)cur.size() == 1) {
            if (id > 0) C[id] = 0;
            else if (id < 0) X[abs(id)] = id, Y[abs(id)] = 0;
            continue;
        }
        if ((int)cur.size() == 2) {
            int to = cur[1];
            if (id > 0) C[id] = to;
            else if (id < 0) X[abs(id)] = id, Y[abs(id)] = to;
            continue;
        }

        if (id > 0) {
            vi nw;
            int scnt = (int)X.size();
            scnt++;
            X.pb(0); Y.pb(0); pr.pb(-scnt);
            nw.pb(-scnt);
            C[id] = -scnt;
            FOR(j, 1, (int)cur.size()-1) nw.pb(cur[j]);
            out.pb(nw);
            continue;
        }

        vi one, two;
        //int scnt = (int)X.size();
        //scnt++;
        //REP(2) {X.pb(0); Y.pb(0);}
        bool b = false;
        //X[id] = -scnt;
        //Y[id] =
        //one.pb(-scnt);
        //two.pb(-(scnt+1));

        int twoPwr = 1;
        while (twoPwr < (int)cur.size()-1) {
            twoPwr *= 2;
        }

        REP(twoPwr - (int)cur.size()+1) {
            if (!b)
                one.pb(INF);
            else
                two.pb(INF);
            b = !b;
        }

        FOR(j, 1, (int)cur.size()-1) {
            if (!b)
                one.pb(cur[j]);
            else
                two.pb(cur[j]);

            b = !b;
        }

        if ((int)one.size() == 1) X[abs(id)-1] = one[0];
        else {
            int scnt = (int)X.size();
            scnt++;
            X.pb(0); Y.pb(0); pr.pb(pr[abs(id)-1]);
            X[abs(id)-1] = -scnt;
            reverse(one.begin(), one.end());
            one.pb(-scnt);
            reverse(one.begin(), one.end());
            out.pb(one);
        }

        if ((int)two.size() == 1) Y[abs(id)-1] = two[0];
        else {
            int scnt = (int)X.size();
            scnt++;
            X.pb(0); Y.pb(0); pr.pb(pr[abs(id)-1]);
            Y[abs(id)-1] = -scnt;
            reverse(two.begin(), two.end());
            two.pb(-scnt);
            reverse(two.begin(), two.end());
            out.pb(two);
        }

        //out.pb(one);
        //out.pb(two);
    }

    FOR(i, 0, (int)X.size()-1) {
        if (X[i] == INF) X[i] = pr[i];
        if (Y[i] == INF) Y[i] = pr[i];
    }

    answer(C, X, Y);
}

/*

4 4
1 2 1 3

*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 78 ms 12300 KB Output is correct
3 Correct 58 ms 10196 KB Output is correct
4 Correct 1 ms 252 KB Output is correct
5 Correct 40 ms 9272 KB Output is correct
6 Correct 92 ms 13780 KB Output is correct
7 Correct 1 ms 236 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 78 ms 12300 KB Output is correct
3 Correct 58 ms 10196 KB Output is correct
4 Correct 1 ms 252 KB Output is correct
5 Correct 40 ms 9272 KB Output is correct
6 Correct 92 ms 13780 KB Output is correct
7 Correct 1 ms 236 KB Output is correct
8 Correct 107 ms 15556 KB Output is correct
9 Correct 155 ms 18316 KB Output is correct
10 Correct 221 ms 23732 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 240 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 78 ms 12300 KB Output is correct
3 Correct 58 ms 10196 KB Output is correct
4 Correct 1 ms 252 KB Output is correct
5 Correct 40 ms 9272 KB Output is correct
6 Correct 92 ms 13780 KB Output is correct
7 Correct 1 ms 236 KB Output is correct
8 Correct 107 ms 15556 KB Output is correct
9 Correct 155 ms 18316 KB Output is correct
10 Correct 221 ms 23732 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 240 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 247 ms 30316 KB Output is correct
15 Correct 123 ms 15640 KB Output is correct
16 Correct 191 ms 22156 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 224 KB Output is correct
19 Correct 1 ms 292 KB Output is correct
20 Correct 204 ms 25808 KB Output is correct
21 Correct 1 ms 244 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 153 ms 21144 KB Output is correct
3 Partially correct 210 ms 39708 KB Output is partially correct
4 Partially correct 253 ms 41528 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 153 ms 21144 KB Output is correct
3 Partially correct 210 ms 39708 KB Output is partially correct
4 Partially correct 253 ms 41528 KB Output is partially correct
5 Partially correct 235 ms 33060 KB Output is partially correct
6 Partially correct 294 ms 36720 KB Output is partially correct
7 Partially correct 270 ms 35380 KB Output is partially correct
8 Partially correct 285 ms 39604 KB Output is partially correct
9 Partially correct 256 ms 38636 KB Output is partially correct
10 Partially correct 305 ms 51464 KB Output is partially correct
11 Partially correct 301 ms 48116 KB Output is partially correct
12 Partially correct 210 ms 30924 KB Output is partially correct
13 Partially correct 150 ms 23728 KB Output is partially correct
14 Partially correct 169 ms 22832 KB Output is partially correct
15 Partially correct 184 ms 21256 KB Output is partially correct
16 Partially correct 4 ms 948 KB Output is partially correct
17 Partially correct 133 ms 23804 KB Output is partially correct
18 Partially correct 143 ms 25312 KB Output is partially correct
19 Partially correct 199 ms 26412 KB Output is partially correct
20 Partially correct 194 ms 32772 KB Output is partially correct
21 Partially correct 289 ms 43004 KB Output is partially correct
22 Partially correct 189 ms 30896 KB Output is partially correct