oj.uz

Submission #1016633

# Submission time Handle Problem Language Result Execution time Memory
1016633 2024-07-08T09:33:09 Z Unforgettablepl Mechanical Doll (IOI18_doll) C++17
75.4031 / 100
 106 ms 12564 KB 
#include <bits/stdc++.h>
using namespace std;

void answer(vector<int> C, vector<int> X, vector<int> Y);

int reverse_bits(int x){
    int res = 0;
    for(int bit=0;bit<=18;bit++)if(x&bit)res|=1<<(30-bit);
    return res;
}

void create_circuit(int M, vector<int> A) {    
    int N = A.size();
    vector<int> C(M + 1,-1);C[0]=A[0];
    vector<int> X(400001),Y(400001);
    vector<int> nextoccurences = A;
    nextoccurences.erase(nextoccurences.begin());
    nextoccurences.emplace_back(0);
    vector<int> perm;
    {
        vector<pair<int,int>> elements;
        int siz = 1;
        while(nextoccurences.size()>siz)siz<<=1;
        int tar = siz-N;
        vector<bool> taken(siz);
        for(int i=0;i<siz;i++)elements.emplace_back(reverse_bits(i),i);
        sort(elements.begin(),elements.end());
        for(int i=0;i<tar;i++)taken[elements[i].second]=true;
        auto iter = nextoccurences.begin();
        for(int i=0;i<siz;i++){
            if(taken[i])perm.emplace_back(-1);
            else perm.emplace_back(*(iter++));
        }
    }
    int S = 1;
    function<void(int,vector<int>)> calc = [&](int x,vector<int> targets){
        if(targets.size()==2){
            X[x] = targets[0];
            Y[x] = targets[1];
        } else {
            vector<int> odds;
            vector<int> evens;
            for(int i=0;i<targets.size();i++)
                if(i&1)odds.emplace_back(targets[i]);
                else evens.emplace_back(targets[i]);
            bool Xworks = false;
            for(int&i:evens)if(i!=-1)Xworks=true;
            bool Yworks = false;
            for(int&i:odds)if(i!=-1)Yworks=true;
            if(Xworks){
                X[x] = -(++S);
                calc(S,evens);
            } else {
                X[x] = -1;
            }
            if(Yworks){
                Y[x] = -(++S);
                calc(S,odds);
            } else {
                Y[x] = -1;
            }
        }
    };
    calc(1,perm);
    X.erase(X.begin());
    Y.erase(Y.begin());
    X.resize(S);
    Y.resize(S);
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:23:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |         while(nextoccurences.size()>siz)siz<<=1;
      |               ~~~~~~~~~~~~~~~~~~~~~^~~~
doll.cpp: In lambda function:
doll.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int i=0;i<targets.size();i++)
      |                         ~^~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 30 ms 7648 KB Output is correct
3 Correct 35 ms 7624 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 7 ms 4696 KB Output is correct
6 Incorrect 46 ms 9052 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 30 ms 7648 KB Output is correct
3 Correct 35 ms 7624 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 7 ms 4696 KB Output is correct
6 Incorrect 46 ms 9052 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 30 ms 7648 KB Output is correct
3 Correct 35 ms 7624 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 7 ms 4696 KB Output is correct
6 Incorrect 46 ms 9052 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3504 KB Output is correct
4 Correct 2 ms 3416 KB Output is correct
5 Correct 2 ms 3416 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct

Subtask #5
15.909183477 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 49 ms 9628 KB Output is correct
3 Correct 70 ms 10948 KB Output is correct
4 Partially correct 88 ms 12364 KB Output is partially correct

Subtask #6
49.493954636 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 49 ms 9628 KB Output is correct
3 Correct 70 ms 10948 KB Output is correct
4 Partially correct 88 ms 12364 KB Output is partially correct
5 Partially correct 106 ms 12564 KB Output is partially correct
6 Partially correct 88 ms 12484 KB Output is partially correct
7 Partially correct 90 ms 12536 KB Output is partially correct
8 Partially correct 83 ms 12480 KB Output is partially correct
9 Partially correct 63 ms 10940 KB Output is partially correct
10 Partially correct 86 ms 12480 KB Output is partially correct
11 Partially correct 83 ms 12444 KB Output is partially correct
12 Correct 62 ms 10940 KB Output is correct
13 Correct 52 ms 9648 KB Output is correct
14 Correct 67 ms 11200 KB Output is correct
15 Correct 65 ms 11188 KB Output is correct
16 Correct 3 ms 3672 KB Output is correct
17 Correct 48 ms 9408 KB Output is correct
18 Correct 55 ms 9720 KB Output is correct
19 Correct 82 ms 11152 KB Output is correct
20 Partially correct 82 ms 12476 KB Output is partially correct
21 Partially correct 93 ms 12476 KB Output is partially correct
22 Partially correct 81 ms 12476 KB Output is partially correct