oj.uz

Submission #771815

# Submission time Handle Problem Language Result Execution time Memory
771815 2023-07-03T09:42:28 Z Amylopectin Mechanical Doll (IOI18_doll) C++14
84 / 100
 88 ms 15984 KB 
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include "doll.h"
// #include "grader.cpp"
using namespace std;
const int mxn = 5e6 + 10;
struct we
{
    int ord,idx;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.ord < r.ord;
}
struct we mat[mxn] = {};
vector<int> cc,xx,yy;
int c[mxn],sw[2][mxn],ru = 1,se[mxn] = {},ta[mxn] = {};
int bui(int cl,int cr,int no)
{
    if(cl == cr)
    {
        se[no] = ta[cl];
        return 0;
    }
    int mid = (cl+cr) / 2;
    bui(cl,mid,no*2);
    bui(mid+1,cr,no*2+1);
    se[no] = se[no*2] + se[no*2+1];
    return 0;
}
int re(int cl,int cr,int no,int cru)
{
    if(cr-cl == 1)
    {
        if(se[no] == 2)
        {
            sw[0][cru] = ta[cl];
            sw[1][cru] = ta[cr];
        }
        else 
        {
            sw[0][cru] = -1;
            sw[1][cru] = ta[cr];
        }
        return 0;
    }
    int mid = (cl+cr) / 2;
    if(se[no*2] == 0)
    {
        sw[0][cru] = -1;
    }
    else 
    {
        sw[0][cru] = -ru;
        ru ++;
        re(cl,mid,no*2,ru-1);
    }
    sw[1][cru] = -ru;
    ru++;
    re(mid+1,cr,no*2+1,ru-1);
    return 0;
}
void create_circuit(int m, vector<int> a)
{
    int i,j,n = a.size(),cdep,h;
    for(i=0; i<n; i++)
    {
        if((1<<i) >= n)
        {
            cdep = i;
            break;
        }
    }
    h = (1<<cdep);
    for(i=h-n; i<h; i++)
    {
        ta[i] = 1;
    }
    bui(0,h-1,1);
    for(i=0; i<h; i++)
    {
        for(j=0; j<cdep; j++)
        {
            if((1<<j) & i)
                mat[i].ord += (1<<(cdep-j-1));
        }
        mat[i].idx = i;
    }
    sort(mat,mat+h,cmp);
    a.push_back(0);
    ru = 1;
    for(i=0; i<h; i++)
    {
        if(mat[i].idx >= h-n)
        {
            ta[mat[i].idx] = a[ru];
            ru ++;
        }
    }
    c[0] = a[0];
    cc.push_back(a[0]);
    ru = 1;
    for(i=1; i<=m; i++)
    {
        c[i] = -1;
        cc.push_back(-1);
    }
    ru ++;
    re(0,h-1,1,1);

    for(i=1; i<ru; i++)
    {
        xx.push_back(sw[0][i]);
        yy.push_back(sw[1][i]);
    }
    answer(cc,xx,yy);
    return ;
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:76:7: warning: 'cdep' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |     h = (1<<cdep);
      |     ~~^~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 31 ms 6336 KB Output is correct
3 Correct 42 ms 7216 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 8 ms 1996 KB Output is correct
6 Correct 48 ms 9560 KB Output is correct
7 Runtime error 3 ms 468 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 31 ms 6336 KB Output is correct
3 Correct 42 ms 7216 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 8 ms 1996 KB Output is correct
6 Correct 48 ms 9560 KB Output is correct
7 Runtime error 3 ms 468 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 31 ms 6336 KB Output is correct
3 Correct 42 ms 7216 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 8 ms 1996 KB Output is correct
6 Correct 48 ms 9560 KB Output is correct
7 Runtime error 3 ms 468 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 47 ms 9024 KB Output is correct
3 Correct 71 ms 10692 KB Output is correct
4 Correct 82 ms 14132 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 47 ms 9024 KB Output is correct
3 Correct 71 ms 10692 KB Output is correct
4 Correct 82 ms 14132 KB Output is correct
5 Correct 87 ms 15984 KB Output is correct
6 Correct 87 ms 15280 KB Output is correct
7 Correct 86 ms 15408 KB Output is correct
8 Correct 85 ms 15196 KB Output is correct
9 Correct 67 ms 10772 KB Output is correct
10 Correct 84 ms 14904 KB Output is correct
11 Correct 85 ms 14496 KB Output is correct
12 Correct 69 ms 11024 KB Output is correct
13 Correct 50 ms 9528 KB Output is correct
14 Correct 70 ms 11648 KB Output is correct
15 Correct 70 ms 11784 KB Output is correct
16 Correct 2 ms 684 KB Output is correct
17 Correct 48 ms 9296 KB Output is correct
18 Correct 48 ms 9168 KB Output is correct
19 Correct 67 ms 10972 KB Output is correct
20 Correct 84 ms 15016 KB Output is correct
21 Correct 88 ms 14420 KB Output is correct
22 Correct 84 ms 14548 KB Output is correct