oj.uz

Submission #771800

# Submission time Handle Problem Language Result Execution time Memory
771800 2023-07-03T09:34:13 Z Amylopectin Mechanical Doll (IOI18_doll) C++14
84 / 100
 123 ms 71788 KB 
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include "doll.h"
// #include "grader.cpp"
using namespace std;
const int mxn = 5e5 + 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> lii[mxn] = {},ou[mxn] = {},xoy[mxn] = {},cc,xx,yy;
int coul[mxn] = {},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 18 ms 35540 KB Output is correct
2 Correct 48 ms 41556 KB Output is correct
3 Correct 55 ms 42464 KB Output is correct
4 Correct 17 ms 35540 KB Output is correct
5 Correct 25 ms 37244 KB Output is correct
6 Correct 65 ms 44768 KB Output is correct
7 Runtime error 44 ms 71788 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 18 ms 35540 KB Output is correct
2 Correct 48 ms 41556 KB Output is correct
3 Correct 55 ms 42464 KB Output is correct
4 Correct 17 ms 35540 KB Output is correct
5 Correct 25 ms 37244 KB Output is correct
6 Correct 65 ms 44768 KB Output is correct
7 Runtime error 44 ms 71788 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 18 ms 35540 KB Output is correct
2 Correct 48 ms 41556 KB Output is correct
3 Correct 55 ms 42464 KB Output is correct
4 Correct 17 ms 35540 KB Output is correct
5 Correct 25 ms 37244 KB Output is correct
6 Correct 65 ms 44768 KB Output is correct
7 Runtime error 44 ms 71788 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 16 ms 35540 KB Output is correct
2 Correct 16 ms 35540 KB Output is correct
3 Correct 16 ms 35552 KB Output is correct
4 Correct 17 ms 35540 KB Output is correct
5 Correct 21 ms 35456 KB Output is correct
6 Correct 17 ms 35540 KB Output is correct
7 Correct 21 ms 35572 KB Output is correct
8 Correct 17 ms 35540 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 35540 KB Output is correct
2 Correct 64 ms 44280 KB Output is correct
3 Correct 96 ms 46064 KB Output is correct
4 Correct 100 ms 49288 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 35540 KB Output is correct
2 Correct 64 ms 44280 KB Output is correct
3 Correct 96 ms 46064 KB Output is correct
4 Correct 100 ms 49288 KB Output is correct
5 Correct 104 ms 51052 KB Output is correct
6 Correct 123 ms 50380 KB Output is correct
7 Correct 104 ms 50508 KB Output is correct
8 Correct 118 ms 50364 KB Output is correct
9 Correct 85 ms 45836 KB Output is correct
10 Correct 101 ms 49964 KB Output is correct
11 Correct 101 ms 49640 KB Output is correct
12 Correct 85 ms 46132 KB Output is correct
13 Correct 69 ms 44756 KB Output is correct
14 Correct 88 ms 46720 KB Output is correct
15 Correct 87 ms 46904 KB Output is correct
16 Correct 19 ms 35924 KB Output is correct
17 Correct 66 ms 44508 KB Output is correct
18 Correct 65 ms 44380 KB Output is correct
19 Correct 90 ms 46060 KB Output is correct
20 Correct 103 ms 50156 KB Output is correct
21 Correct 104 ms 49520 KB Output is correct
22 Correct 101 ms 49624 KB Output is correct