oj.uz

Submission #1016660

# Submission time Handle Problem Language Result Execution time Memory
1016660 2024-07-08T10:08:11 Z Unforgettablepl Mechanical Doll (IOI18_doll) C++17
100 / 100
 117 ms 13532 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<=20;bit++)if(x&(1<<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 = 2;
        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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 33 ms 7628 KB Output is correct
3 Correct 37 ms 7360 KB Output is correct
4 Correct 2 ms 3416 KB Output is correct
5 Correct 7 ms 4700 KB Output is correct
6 Correct 49 ms 8876 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 33 ms 7628 KB Output is correct
3 Correct 37 ms 7360 KB Output is correct
4 Correct 2 ms 3416 KB Output is correct
5 Correct 7 ms 4700 KB Output is correct
6 Correct 49 ms 8876 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 57 ms 9664 KB Output is correct
9 Correct 92 ms 11576 KB Output is correct
10 Correct 94 ms 13532 KB Output is correct
11 Correct 2 ms 3420 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct
13 Correct 2 ms 3420 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 33 ms 7628 KB Output is correct
3 Correct 37 ms 7360 KB Output is correct
4 Correct 2 ms 3416 KB Output is correct
5 Correct 7 ms 4700 KB Output is correct
6 Correct 49 ms 8876 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 57 ms 9664 KB Output is correct
9 Correct 92 ms 11576 KB Output is correct
10 Correct 94 ms 13532 KB Output is correct
11 Correct 2 ms 3420 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct
13 Correct 2 ms 3420 KB Output is correct
14 Correct 89 ms 12732 KB Output is correct
15 Correct 76 ms 11204 KB Output is correct
16 Correct 89 ms 12464 KB Output is correct
17 Correct 2 ms 3416 KB Output is correct
18 Correct 2 ms 3420 KB Output is correct
19 Correct 2 ms 3420 KB Output is correct
20 Correct 89 ms 12736 KB Output is correct
21 Correct 2 ms 3420 KB Output is correct
22 Correct 1 ms 3420 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 56 ms 9412 KB Output is correct
3 Correct 70 ms 10944 KB Output is correct
4 Correct 117 ms 11964 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 56 ms 9412 KB Output is correct
3 Correct 70 ms 10944 KB Output is correct
4 Correct 117 ms 11964 KB Output is correct
5 Correct 97 ms 12228 KB Output is correct
6 Correct 95 ms 11972 KB Output is correct
7 Correct 102 ms 12068 KB Output is correct
8 Correct 98 ms 12100 KB Output is correct
9 Correct 78 ms 10920 KB Output is correct
10 Correct 111 ms 12092 KB Output is correct
11 Correct 98 ms 12048 KB Output is correct
12 Correct 71 ms 10788 KB Output is correct
13 Correct 54 ms 9412 KB Output is correct
14 Correct 109 ms 10864 KB Output is correct
15 Correct 70 ms 10948 KB Output is correct
16 Correct 4 ms 3672 KB Output is correct
17 Correct 54 ms 9300 KB Output is correct
18 Correct 51 ms 9408 KB Output is correct
19 Correct 68 ms 10952 KB Output is correct
20 Correct 108 ms 12064 KB Output is correct
21 Correct 87 ms 11952 KB Output is correct
22 Correct 86 ms 11964 KB Output is correct