oj.uz

Submission #330548

# Submission time Handle Problem Language Result Execution time Memory
330548 2020-11-25T17:17:11 Z lLab_ Mechanical Doll (IOI18_doll) C++14
10 / 100
 2 ms 204 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> X,Y,C;
int cnt = 0;

int createS(int x,int y){
    cnt--;
    X.push_back(x);
    Y.push_back(y);
    return cnt;
}

int create(vector<int> v){
    bool ok = true;
    for(int i=1;i<v.size();++i){
        if(v[i] != v[i-1]){
            ok = false;
            break;
        }
    }
    if(v.size() == 1 || ok){
        return v[0];
    }

    vector<int> x,y;
    for(int i=0;i<v.size();++i){
        if(i%2==0) x.push_back(v[i]);
        else y.push_back(v[i]);
    }

    int l = create(x);
    int r = create(y);

    return createS(l,r);
}

int rev(int k,int n){
    int B = 0;
    for(int i=0;i<k;++i){
        B <<= 1;
        B = n&1;
        n >>= 1;
    }
    return B;
}

void create_circuit(int M,vector<int> A) {
    int N = A.size();
    int nn = 0;

    while(1<<nn < N){
        nn++;
    }
    int k = nn;
    nn = 1<<nn;

    vector<int> v(nn,0);

    for(int i=0;i<nn-N;++i){
        v[rev(k,i)] = 2e9;
    }

    int curr = 0;
    for(int i=1;i<A.size();++i){
        while(v[curr] == 2e9) curr++;
        v[curr] = A[i];
        curr++;
    }

    v[nn-1] = 0;

    int root = create(v);

    for(int i=0;i<X.size();++i){
        if(X[i] == 2e9) X[i] = root;
    }
    for(int i=0;i<Y.size();++i){
        if(Y[i] == 2e9) Y[i] = root;
    }

    C.resize(M+1,root);
    C[0] = A[0];

    return answer(C,X,Y);
}

Compilation message

doll.cpp: In function 'int create(std::vector<int>)':
doll.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=1;i<v.size();++i){
      |                 ~^~~~~~~~~
doll.cpp:28:18: 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=0;i<v.size();++i){
      |                 ~^~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i=1;i<A.size();++i){
      |                 ~^~~~~~~~~
doll.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0;i<X.size();++i){
      |                 ~^~~~~~~~~
doll.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0;i<Y.size();++i){
      |                 ~^~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0.0 / 18.0

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

Subtask #6
0.0 / 56.0

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