oj.uz

Submission #1016625

# Submission time Handle Problem Language Result Execution time Memory
1016625 2024-07-08T09:25:04 Z Unforgettablepl Mechanical Doll (IOI18_doll) C++17
10 / 100
 3 ms 3420 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=1;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-1]=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 Incorrect 2 ms 3420 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3420 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3420 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 3 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 3416 KB Output is correct

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3420 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3420 KB state 'Y'
2 Halted 0 ms 0 KB -