oj.uz

Submission #293822

# Submission time Handle Problem Language Result Execution time Memory
293822 2020-09-08T12:40:06 Z Atill83 Mechanical Doll (IOI18_doll) C++14
100 / 100
 194 ms 24644 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)2e6 + 5;
int cur = -1;
vector<int> X, Y, C;

int do_it(vector<int> & sm){
    int ad = cur--;
    int nxPw = sm.size();

    while(nxPw == 1 || __builtin_popcount(nxPw) != 1)
        nxPw++;
    int kal = nxPw - sm.size();
    vector<int> nw(nxPw, 313131313);
    if(ad == -1){
        vector<int> pws;
        int mxP;
        for(int j = 20; j >= 0; j--){
            if((1<<j) & nxPw) mxP = j;
            if((1<<j) & kal){
                pws.push_back(j);
            }
        }
        int kt = 0;
        for(int j: pws){
            int cur = (1<<(mxP - j));
            for(int i = kt; i < nw.size(); i += cur) nw[i] = -1;
            kt++;
            kt *= 2;
        }
        int curB = 0;
        for(int l: sm){
            while(nw[curB] != 313131313) 
                curB++;
            nw[curB] = l;
        }
    }else{
        for(int i = 0; i < nw.size(); i++) 
            nw[i] = sm[i];
    }




    int deg = 0;

    for(int i = 1; i < nw.size(); i++){
        deg += (nw[i] != nw[i - 1]);
    }
    if(!deg){
        cur++;
        return nw[0];
    }
    if(nw.size() == 2){
        X[-ad - 1] = nw[0];
        Y[-ad - 1] = nw[1];
        return ad;
    }
    vector<int> ot1, ot2;
    for(int i = 0; i < nw.size(); i+=2)
        ot1.push_back(nw[i]);
    for(int i = 1; i < nw.size(); i+=2)
        ot2.push_back(nw[i]);
    int a = do_it(ot1), b = do_it(ot2);
    X[-ad - 1] = a;
    Y[-ad - 1] = b;
    return ad;
}


void create_circuit(int M, vector<int> A){
    A.push_back(0);
    int N = A.size();
    X.resize(MAXN, 0);
    Y.resize(MAXN, 0);
    C.resize(M + 1, 0);
    C[0] = do_it(A);
    for(int i = 1; i <= M; i++) C[i] = C[0];
    X.resize(-cur - 1);
    Y.resize(-cur - 1);
    /*for(int i = 0; i < X.size(); i++){
        cerr<<X[i]<<" "<<Y[i]<<endl;
    }*/
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'int do_it(std::vector<int>&)':
doll.cpp:28:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |             for(int i = kt; i < nw.size(); i += cur) nw[i] = -1;
      |                             ~~^~~~~~~~~~~
doll.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i = 0; i < nw.size(); i++)
      |                        ~~^~~~~~~~~~~
doll.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 1; i < nw.size(); i++){
      |                    ~~^~~~~~~~~~~
doll.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 0; i < nw.size(); i+=2)
      |                    ~~^~~~~~~~~~~
doll.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 1; i < nw.size(); i+=2)
      |                    ~~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:74:9: warning: unused variable 'N' [-Wunused-variable]
   74 |     int N = A.size();
      |         ^
doll.cpp: In function 'int do_it(std::vector<int>&)':
doll.cpp:27:32: warning: 'mxP' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |             int cur = (1<<(mxP - j));
      |                           ~~~~~^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15948 KB Output is correct
2 Correct 66 ms 19668 KB Output is correct
3 Correct 73 ms 19220 KB Output is correct
4 Correct 13 ms 15916 KB Output is correct
5 Correct 22 ms 17100 KB Output is correct
6 Correct 81 ms 20956 KB Output is correct
7 Correct 11 ms 15948 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15948 KB Output is correct
2 Correct 66 ms 19668 KB Output is correct
3 Correct 73 ms 19220 KB Output is correct
4 Correct 13 ms 15916 KB Output is correct
5 Correct 22 ms 17100 KB Output is correct
6 Correct 81 ms 20956 KB Output is correct
7 Correct 11 ms 15948 KB Output is correct
8 Correct 100 ms 21676 KB Output is correct
9 Correct 102 ms 21844 KB Output is correct
10 Correct 139 ms 24644 KB Output is correct
11 Correct 11 ms 15948 KB Output is correct
12 Correct 11 ms 15888 KB Output is correct
13 Correct 12 ms 15948 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15948 KB Output is correct
2 Correct 66 ms 19668 KB Output is correct
3 Correct 73 ms 19220 KB Output is correct
4 Correct 13 ms 15916 KB Output is correct
5 Correct 22 ms 17100 KB Output is correct
6 Correct 81 ms 20956 KB Output is correct
7 Correct 11 ms 15948 KB Output is correct
8 Correct 100 ms 21676 KB Output is correct
9 Correct 102 ms 21844 KB Output is correct
10 Correct 139 ms 24644 KB Output is correct
11 Correct 11 ms 15948 KB Output is correct
12 Correct 11 ms 15888 KB Output is correct
13 Correct 12 ms 15948 KB Output is correct
14 Correct 153 ms 23680 KB Output is correct
15 Correct 138 ms 21400 KB Output is correct
16 Correct 136 ms 23588 KB Output is correct
17 Correct 10 ms 15948 KB Output is correct
18 Correct 12 ms 15844 KB Output is correct
19 Correct 11 ms 15948 KB Output is correct
20 Correct 147 ms 23776 KB Output is correct
21 Correct 10 ms 15852 KB Output is correct
22 Correct 12 ms 15948 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15920 KB Output is correct
2 Correct 14 ms 15880 KB Output is correct
3 Correct 12 ms 15964 KB Output is correct
4 Correct 10 ms 15948 KB Output is correct
5 Correct 12 ms 15956 KB Output is correct
6 Correct 11 ms 15948 KB Output is correct
7 Correct 11 ms 15948 KB Output is correct
8 Correct 11 ms 15948 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15948 KB Output is correct
2 Correct 34 ms 21064 KB Output is correct
3 Correct 36 ms 21032 KB Output is correct
4 Correct 49 ms 21540 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15948 KB Output is correct
2 Correct 34 ms 21064 KB Output is correct
3 Correct 36 ms 21032 KB Output is correct
4 Correct 49 ms 21540 KB Output is correct
5 Correct 135 ms 23436 KB Output is correct
6 Correct 134 ms 23324 KB Output is correct
7 Correct 141 ms 23312 KB Output is correct
8 Correct 136 ms 23060 KB Output is correct
9 Correct 85 ms 21056 KB Output is correct
10 Correct 127 ms 22036 KB Output is correct
11 Correct 194 ms 22940 KB Output is correct
12 Correct 89 ms 21004 KB Output is correct
13 Correct 109 ms 21264 KB Output is correct
14 Correct 103 ms 21276 KB Output is correct
15 Correct 97 ms 21308 KB Output is correct
16 Correct 12 ms 16104 KB Output is correct
17 Correct 98 ms 20436 KB Output is correct
18 Correct 95 ms 21184 KB Output is correct
19 Correct 98 ms 21088 KB Output is correct
20 Correct 136 ms 22924 KB Output is correct
21 Correct 133 ms 22816 KB Output is correct
22 Correct 136 ms 22800 KB Output is correct