oj.uz

Submission #615981

# Submission time Handle Problem Language Result Execution time Memory
615981 2022-07-31T17:05:51 Z neki Mechanical Doll (IOI18_doll) C++14
100 / 100
 116 ms 10768 KB 
#include "doll.h"
#include <bits/stdc++.h>
#define vc vector

using namespace std;

/*void answer(vc<int> c, vc<int> x, vc<int> y){
    for(auto v: c) cout << v << " ";cout << endl;
    for(auto v: x) cout << v << " ";cout << endl;
    for(auto v: y) cout << v << " ";cout << endl;
}*/

int rev(int x, const int k){
    int ret=0;
    for(int i=0;i<k;++i) if(x&(1<<i)) ret+=(1<<(k-i-1));
    return ret;
}

void create_circuit(int m, vc<int> a){
    a.push_back(0);
    
    int k=0;
    while(a.size()>(1<<k)) ++k;
    int zac=(1<<k) -(int) a.size();
    
    //cout << zac << " "<< k <<" " << a.size() << endl;
    
    vc<int> x, y;
    int cnt=0;
    vc<pair<int, int>> red(1<<k, make_pair(-1, -1));
    int bla=0;
    function<int (int, int)> solve=[&](int l, int r){
        int mojid=++cnt;
        int mid=(l+r)/2;
        x.push_back(INT_MAX), y.push_back(INT_MAX);
        
        if(r-l==2){
            if(l>=zac)  red[rev(l, k)]=make_pair(mojid-1, 0);
            else x[mojid-1]=-1;
            red[rev(l+1, k)]=make_pair(mojid-1, 1);
        }
        else{
            if(mid<=zac)  x[mojid-1]=-1;
            else x[mojid-1]=-solve(l, mid);
            y[mojid-1]=-solve(mid, r);
        }
        return mojid;
    };
    solve(0, 1<<k);
    
    for(int i=0, cur=0;i<(1<<k);++i) if(red[i]!=make_pair(-1, -1)){
        //cout << red[i].first << " ";
        if(red[i].second==0) x[red[i].first]=a[cur++];
        if(red[i].second==1) y[red[i].first]=a[cur++];
        //cout << cur << " ";
    }
    //cout << endl;
    
    answer(vc<int>(m+1, -1), x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:23:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |     while(a.size()>(1<<k)) ++k;
      |           ~~~~~~~~^~~~~~~
doll.cpp:31:9: warning: unused variable 'bla' [-Wunused-variable]
   31 |     int bla=0;
      |         ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 37 ms 4808 KB Output is correct
3 Correct 28 ms 4596 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 980 KB Output is correct
6 Correct 41 ms 5952 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 37 ms 4808 KB Output is correct
3 Correct 28 ms 4596 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 980 KB Output is correct
6 Correct 41 ms 5952 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 52 ms 7884 KB Output is correct
9 Correct 53 ms 8180 KB Output is correct
10 Correct 100 ms 10768 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 37 ms 4808 KB Output is correct
3 Correct 28 ms 4596 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 980 KB Output is correct
6 Correct 41 ms 5952 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 52 ms 7884 KB Output is correct
9 Correct 53 ms 8180 KB Output is correct
10 Correct 100 ms 10768 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 79 ms 10544 KB Output is correct
15 Correct 53 ms 7612 KB Output is correct
16 Correct 74 ms 10428 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 78 ms 10716 KB Output is correct
21 Correct 1 ms 304 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 68 ms 7280 KB Output is correct
3 Correct 48 ms 7412 KB Output is correct
4 Correct 67 ms 10012 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 68 ms 7280 KB Output is correct
3 Correct 48 ms 7412 KB Output is correct
4 Correct 67 ms 10012 KB Output is correct
5 Correct 76 ms 10400 KB Output is correct
6 Correct 116 ms 10184 KB Output is correct
7 Correct 77 ms 10188 KB Output is correct
8 Correct 72 ms 10080 KB Output is correct
9 Correct 46 ms 7372 KB Output is correct
10 Correct 69 ms 10124 KB Output is correct
11 Correct 67 ms 10012 KB Output is correct
12 Correct 43 ms 7308 KB Output is correct
13 Correct 44 ms 7492 KB Output is correct
14 Correct 59 ms 7600 KB Output is correct
15 Correct 48 ms 7532 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 42 ms 6608 KB Output is correct
18 Correct 47 ms 7380 KB Output is correct
19 Correct 57 ms 7288 KB Output is correct
20 Correct 68 ms 10024 KB Output is correct
21 Correct 73 ms 10000 KB Output is correct
22 Correct 72 ms 9988 KB Output is correct