oj.uz

Submission #885753

# Submission time Handle Problem Language Result Execution time Memory
885753 2023-12-10T15:56:00 Z JakobZorz Mechanical Doll (IOI18_doll) C++17
100 / 100
 133 ms 13328 KB 
#include"doll.h"
#include<iostream>
#include<algorithm>
using namespace std;
 
vector<int>sx,sy;
vector<int>arr;
 
int new_switch(){
    sx.push_back(0);
    sy.push_back(0);
    return(int)sx.size()-1;
}
 
pair<vector<int>,vector<int>>split(vector<int>vec){
    pair<vector<int>,vector<int>>res;
    for(int i=0;i<vec.size();i++){
        if(i%2==0)
            res.first.push_back(vec[i]);
        else
            res.second.push_back(vec[i]);
    }
    return res;
}

vector<int>get_cancelled(int size,int cancelled){
    if(size==1&&cancelled==0)
        return{0};
    if(size==1&&cancelled==1)
        return{-1};
    
    vector<int>vec1=get_cancelled(size/2,min(cancelled,size/2));
    vector<int>vec2=get_cancelled(size/2,max(cancelled-size/2,0));
    vector<int>vec;
    for(int i=0;i<size/2;i++){
        vec.push_back(vec1[i]);
        vec.push_back(vec2[i]);
    }
    return vec;
}

int build(vector<int>exits){
    bool all_same=true;
    for(int i=0;i<(int)exits.size()-1;i++)
        if(exits[i]!=exits[i+1])
            all_same=false;
    
    if(all_same)
        return exits[0];
    
    int root=new_switch();
    
    pair<vector<int>,vector<int>>res=split(exits);
    sx[root]=build(res.first);
    sy[root]=build(res.second);
    
    return -root-1;
}
 
void create_circuit(int m,vector<int>_arr){
    arr=_arr;
    int n=(int)arr.size();
    
    vector<int>ans(m+1);
    
    vector<int>exits=arr;
    exits.push_back(0);
    reverse(exits.begin(),exits.end());
    int pow2=1;
    while(pow2<(int)exits.size())
        pow2*=2;
    
    vector<int>exits2=get_cancelled(pow2,pow2-(int)exits.size());
    for(int&i:exits2){
        if(i==0){
            i=exits.back();
            exits.pop_back();
        }
    }
    
    
    int root=build(exits2);
    for(int&i:ans)
        i=root;
    
    answer(ans,sx,sy);
}

Compilation message

doll.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > split(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=0;i<vec.size();i++){
      |                 ~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:62:9: warning: unused variable 'n' [-Wunused-variable]
   62 |     int n=(int)arr.size();
      |         ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 46 ms 6100 KB Output is correct
3 Correct 44 ms 5844 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 58 ms 8260 KB Output is correct
7 Correct 1 ms 600 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 46 ms 6100 KB Output is correct
3 Correct 44 ms 5844 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 58 ms 8260 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 107 ms 10948 KB Output is correct
9 Correct 85 ms 11212 KB Output is correct
10 Correct 110 ms 12728 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 46 ms 6100 KB Output is correct
3 Correct 44 ms 5844 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 58 ms 8260 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 107 ms 10948 KB Output is correct
9 Correct 85 ms 11212 KB Output is correct
10 Correct 110 ms 12728 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 109 ms 12676 KB Output is correct
15 Correct 81 ms 10952 KB Output is correct
16 Correct 108 ms 12528 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 110 ms 12732 KB Output is correct
21 Correct 0 ms 684 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 40 ms 8528 KB Output is correct
3 Correct 40 ms 8392 KB Output is correct
4 Correct 47 ms 9916 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 40 ms 8528 KB Output is correct
3 Correct 40 ms 8392 KB Output is correct
4 Correct 47 ms 9916 KB Output is correct
5 Correct 111 ms 12440 KB Output is correct
6 Correct 107 ms 13328 KB Output is correct
7 Correct 133 ms 12548 KB Output is correct
8 Correct 105 ms 13216 KB Output is correct
9 Correct 75 ms 9932 KB Output is correct
10 Correct 115 ms 12936 KB Output is correct
11 Correct 105 ms 12272 KB Output is correct
12 Correct 78 ms 10176 KB Output is correct
13 Correct 80 ms 10696 KB Output is correct
14 Correct 80 ms 10696 KB Output is correct
15 Correct 84 ms 10892 KB Output is correct
16 Correct 3 ms 600 KB Output is correct
17 Correct 62 ms 8520 KB Output is correct
18 Correct 78 ms 10428 KB Output is correct
19 Correct 78 ms 10292 KB Output is correct
20 Correct 106 ms 13208 KB Output is correct
21 Correct 112 ms 12320 KB Output is correct
22 Correct 110 ms 12216 KB Output is correct