oj.uz

Submission #885718

# Submission time Handle Problem Language Result Execution time Memory
885718 2023-12-10T14:36:09 Z JakobZorz Mechanical Doll (IOI18_doll) C++17
53 / 100
 134 ms 18048 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;
}

int build(vector<int>exits){
    int root=new_switch();
    
    if(exits.size()==2){
        sx[root]=exits[0];
        sy[root]=exits[1];
        return -root-1;
    }
    
    pair<vector<int>,vector<int>>res=split(exits);
    sx[root]=build(res.first);
    sy[root]=build(res.second);
    
    return -root-1;
}

int handle(vector<int>exits){
    if(exits.size()==0)
        return 0;
    
    if(exits.size()==1)
        return exits[0];
    
    reverse(exits.begin(),exits.end());
    int pow2=1;
    while(pow2<(int)exits.size())
        pow2*=2;
    int root=new_switch();
    while(exits.size()<pow2)
        exits.push_back(-root-1);
    reverse(exits.begin(),exits.end());
    
    if(exits.size()==2){
        sx[root]=exits[0];
        sy[root]=exits[1];
        return -root-1;
    }
    
    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<vector<int>>occ(m+1);
    for(int i=0;i<n;i++)
        occ[arr[i]].push_back(i);
    
    vector<int>ans(m+1);
    ans[0]=arr[0];
    
    for(int i=1;i<=m;i++){
        vector<int>exits;
        for(int j:occ[i]){
            if(j==n-1)
                exits.push_back(0);
            else
                exits.push_back(arr[j+1]);
        }
        /*cout<<i<<": ";
        for(int i:occ[i])
            cout<<i<<" ";
        cout<<"\n";*/
        ans[i]=handle(exits);
    }
    
    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 'int handle(std::vector<int>)':
doll.cpp:54:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |     while(exits.size()<pow2)
      |           ~~~~~~~~~~~~^~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 22 ms 7056 KB Output is correct
3 Correct 18 ms 5980 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 9 ms 3760 KB Output is correct
6 Correct 29 ms 9200 KB Output is correct
7 Correct 1 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 22 ms 7056 KB Output is correct
3 Correct 18 ms 5980 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 9 ms 3760 KB Output is correct
6 Correct 29 ms 9200 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 39 ms 8696 KB Output is correct
9 Correct 38 ms 10156 KB Output is correct
10 Correct 59 ms 13256 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 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 348 KB Output is correct
2 Correct 22 ms 7056 KB Output is correct
3 Correct 18 ms 5980 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 9 ms 3760 KB Output is correct
6 Correct 29 ms 9200 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 39 ms 8696 KB Output is correct
9 Correct 38 ms 10156 KB Output is correct
10 Correct 59 ms 13256 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 87 ms 13208 KB Output is correct
15 Correct 40 ms 7376 KB Output is correct
16 Correct 61 ms 10940 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 68 ms 12920 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Correct 46 ms 7764 KB Output is correct
3 Partially correct 98 ms 12928 KB Output is partially correct
4 Partially correct 84 ms 13816 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Correct 46 ms 7764 KB Output is correct
3 Partially correct 98 ms 12928 KB Output is partially correct
4 Partially correct 84 ms 13816 KB Output is partially correct
5 Partially correct 96 ms 14560 KB Output is partially correct
6 Partially correct 119 ms 15716 KB Output is partially correct
7 Partially correct 102 ms 15384 KB Output is partially correct
8 Partially correct 114 ms 16560 KB Output is partially correct
9 Partially correct 79 ms 10736 KB Output is partially correct
10 Partially correct 116 ms 18048 KB Output is partially correct
11 Partially correct 134 ms 17020 KB Output is partially correct
12 Partially correct 75 ms 11104 KB Output is partially correct
13 Partially correct 73 ms 10500 KB Output is partially correct
14 Partially correct 66 ms 10108 KB Output is partially correct
15 Partially correct 61 ms 9688 KB Output is partially correct
16 Partially correct 2 ms 700 KB Output is partially correct
17 Partially correct 72 ms 9032 KB Output is partially correct
18 Partially correct 61 ms 9124 KB Output is partially correct
19 Partially correct 68 ms 9712 KB Output is partially correct
20 Partially correct 85 ms 12728 KB Output is partially correct
21 Partially correct 104 ms 14920 KB Output is partially correct
22 Partially correct 79 ms 11740 KB Output is partially correct