oj.uz

Submission #430186

# Submission time Handle Problem Language Result Execution time Memory
430186 2021-06-16T11:57:29 Z TLP39 Mechanical Doll (IOI18_doll) C++14
100 / 100
 125 ms 13884 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

int n;
int a[200010];
int sta=0;
int cur=-1;
int seg[1200040];
int ord[300010];
int cou=0;
vector<int> ss;
int sw(int k)
{
    int ans=0;
    for(int i=0;i<sta;i++)
    {
            if((k>>i)&1) ans+=1<<(sta-1-i);
    }
    return ans;
}

vector<int> toadd;
void build(int v,int st,int ed)
{
    if(ed<(1<<sta)-n)
    {
        seg[v]=-1;
        return;
    }
    if(st==ed)
    {
        seg[v]=a[ord[st]];
        return;
    }
    int mid=(st+ed)>>1;
    seg[v]=cur;
    cur--;
    toadd.push_back(v);
    build(2*v,st,mid);
    build(2*v+1,mid+1,ed);
}

void create_circuit(int M, std::vector<int> A) {
    n=A.size()+1;
    for(int i=0;i<A.size();i++)
    {
        a[i]=A[i];
    }
    a[n-1]=0;
    if(n==2)
    {
        vector<int> c(M+1,0),x,y;
        c[0]=A[0];
        answer(c,x,y);
        return;
    }
    while((1<<sta)<n) sta++;
    for(int i=0;i<(1<<sta);i++) ss.push_back(sw(i));
    for(int i=0;i<ss.size();i++)
    {
        if(ss[i]>=(1<<sta)-n)
        {
            ord[ss[i]]=cou;cou++;
        }
    }
    build(1,0,(1<<sta)-1);
    vector<int> c(M+1,-1),x(-cur-1),y(-cur-1);
    for(int i=0;i<toadd.size();i++)
    {
        x[-1-seg[toadd[i]]]=seg[2*toadd[i]];
        y[-1-seg[toadd[i]]]=seg[2*toadd[i]+1];
    }
    answer(c,x,y);
}

Compilation message

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 47 ms 5420 KB Output is correct
3 Correct 49 ms 5696 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 67 ms 7212 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 47 ms 5420 KB Output is correct
3 Correct 49 ms 5696 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 67 ms 7212 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 77 ms 10168 KB Output is correct
9 Correct 86 ms 10620 KB Output is correct
10 Correct 125 ms 12668 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 256 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 47 ms 5420 KB Output is correct
3 Correct 49 ms 5696 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1484 KB Output is correct
6 Correct 67 ms 7212 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 77 ms 10168 KB Output is correct
9 Correct 86 ms 10620 KB Output is correct
10 Correct 125 ms 12668 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 122 ms 12312 KB Output is correct
15 Correct 74 ms 10572 KB Output is correct
16 Correct 111 ms 13628 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 112 ms 13884 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 256 KB Output is correct

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 1 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
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 69 ms 8788 KB Output is correct
3 Correct 91 ms 9620 KB Output is correct
4 Correct 102 ms 13104 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 69 ms 8788 KB Output is correct
3 Correct 91 ms 9620 KB Output is correct
4 Correct 102 ms 13104 KB Output is correct
5 Correct 113 ms 13504 KB Output is correct
6 Correct 118 ms 13216 KB Output is correct
7 Correct 125 ms 13348 KB Output is correct
8 Correct 116 ms 13096 KB Output is correct
9 Correct 86 ms 9548 KB Output is correct
10 Correct 120 ms 13080 KB Output is correct
11 Correct 102 ms 13104 KB Output is correct
12 Correct 69 ms 9928 KB Output is correct
13 Correct 99 ms 10260 KB Output is correct
14 Correct 76 ms 10388 KB Output is correct
15 Correct 76 ms 10488 KB Output is correct
16 Correct 4 ms 588 KB Output is correct
17 Correct 63 ms 8564 KB Output is correct
18 Correct 86 ms 9860 KB Output is correct
19 Correct 83 ms 9880 KB Output is correct
20 Correct 102 ms 13092 KB Output is correct
21 Correct 96 ms 13100 KB Output is correct
22 Correct 102 ms 13156 KB Output is correct