oj.uz

Submission #461395

# Submission time Handle Problem Language Result Execution time Memory
461395 2021-08-10T01:01:56 Z urd05 Mechanical Doll (IOI18_doll) C++17
53 / 100
 194 ms 29728 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<int> v;
vector<int> x;
vector<int> y;
vector<int> nt[100001];
int now=-1;
 
void func(int st,vector<int> vec) {
    if (vec.empty()) {
        return;
    }
    if (vec.size()==2) {
        x[-st-1]=vec[0];
        y[-st-1]=vec[1];
        return;
    }
    int nt1,nt2;
    x[-st-1]=now;
    nt1=now;
    now--;
    y[-st-1]=now;
    nt2=now;
    now--;
    vector<int> v1;
    vector<int> v2;
    for(int i=0;i<vec.size();i++) {
        if (i%2==0) {
            v1.push_back(vec[i]);
        }
        else {
            v2.push_back(vec[i]);
        }
    }
    func(nt1,v1);
    func(nt2,v2);
}
 
void create_circuit(int m,vector<int> a) {
    int n=a.size();
    v.resize(m+1);
    x.resize(2000000);
    y.resize(2000000);
    nt[0].push_back(a[0]);
    for(int i=1;i<n;i++) {
        nt[a[i-1]].push_back(a[i]);
    }
    nt[a[n-1]].push_back(0);
    for(int i=0;i<=m;i++) {
        if (nt[i].empty()) {
            v[i]=0;
            continue;
        }
        if (nt[i].size()==1) {
            v[i]=nt[i][0];
            continue;
        }
        v[i]=now;
        now--;
        int sz=nt[i].size();
        int newsz=1;
        while (newsz<sz) {
            newsz*=2;
        }
        nt[i].resize(newsz);
        for(int j=newsz-1;j>=0;j--) {
            if (j>=newsz-sz) {
                nt[i][j]=nt[i][j-newsz+sz];
            }
            else {
                nt[i][j]=v[i];
            }
        }
        func(v[i],nt[i]);
    }
    x.resize(-now-1);
    y.resize(-now-1);
    assert(now>=-400001);
    answer(v,x,y);
}

Compilation message

doll.cpp: In function 'void func(int, std::vector<int>)':
doll.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<vec.size();i++) {
      |                 ~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18244 KB Output is correct
2 Correct 36 ms 22004 KB Output is correct
3 Correct 31 ms 21632 KB Output is correct
4 Correct 9 ms 18272 KB Output is correct
5 Correct 20 ms 19404 KB Output is correct
6 Correct 60 ms 23272 KB Output is correct
7 Correct 9 ms 18252 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18244 KB Output is correct
2 Correct 36 ms 22004 KB Output is correct
3 Correct 31 ms 21632 KB Output is correct
4 Correct 9 ms 18272 KB Output is correct
5 Correct 20 ms 19404 KB Output is correct
6 Correct 60 ms 23272 KB Output is correct
7 Correct 9 ms 18252 KB Output is correct
8 Correct 60 ms 23112 KB Output is correct
9 Correct 62 ms 23892 KB Output is correct
10 Correct 105 ms 25672 KB Output is correct
11 Correct 8 ms 18252 KB Output is correct
12 Correct 9 ms 18252 KB Output is correct
13 Correct 8 ms 18252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18244 KB Output is correct
2 Correct 36 ms 22004 KB Output is correct
3 Correct 31 ms 21632 KB Output is correct
4 Correct 9 ms 18272 KB Output is correct
5 Correct 20 ms 19404 KB Output is correct
6 Correct 60 ms 23272 KB Output is correct
7 Correct 9 ms 18252 KB Output is correct
8 Correct 60 ms 23112 KB Output is correct
9 Correct 62 ms 23892 KB Output is correct
10 Correct 105 ms 25672 KB Output is correct
11 Correct 8 ms 18252 KB Output is correct
12 Correct 9 ms 18252 KB Output is correct
13 Correct 8 ms 18252 KB Output is correct
14 Correct 116 ms 26412 KB Output is correct
15 Correct 68 ms 22296 KB Output is correct
16 Correct 112 ms 24404 KB Output is correct
17 Correct 9 ms 18260 KB Output is correct
18 Correct 9 ms 18252 KB Output is correct
19 Correct 8 ms 18252 KB Output is correct
20 Correct 111 ms 25800 KB Output is correct
21 Correct 9 ms 18252 KB Output is correct
22 Correct 10 ms 18240 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 18252 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 8 ms 18308 KB Output is partially correct
2 Correct 77 ms 22984 KB Output is correct
3 Partially correct 135 ms 27532 KB Output is partially correct
4 Partially correct 138 ms 27804 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 18308 KB Output is partially correct
2 Correct 77 ms 22984 KB Output is correct
3 Partially correct 135 ms 27532 KB Output is partially correct
4 Partially correct 138 ms 27804 KB Output is partially correct
5 Partially correct 145 ms 28000 KB Output is partially correct
6 Partially correct 172 ms 28932 KB Output is partially correct
7 Partially correct 152 ms 28540 KB Output is partially correct
8 Partially correct 192 ms 29056 KB Output is partially correct
9 Partially correct 128 ms 26900 KB Output is partially correct
10 Partially correct 194 ms 29728 KB Output is partially correct
11 Partially correct 181 ms 29316 KB Output is partially correct
12 Partially correct 123 ms 25556 KB Output is partially correct
13 Partially correct 123 ms 25124 KB Output is partially correct
14 Partially correct 101 ms 24856 KB Output is partially correct
15 Partially correct 98 ms 24680 KB Output is partially correct
16 Partially correct 11 ms 18380 KB Output is partially correct
17 Partially correct 99 ms 23836 KB Output is partially correct
18 Partially correct 102 ms 23852 KB Output is partially correct
19 Partially correct 109 ms 24280 KB Output is partially correct
20 Partially correct 140 ms 25996 KB Output is partially correct
21 Partially correct 166 ms 27724 KB Output is partially correct
22 Partially correct 135 ms 25280 KB Output is partially correct