oj.uz

Submission #771830

# Submission time Handle Problem Language Result Execution time Memory
771830 2023-07-03T10:01:18 Z Amylopectin Mechanical Doll (IOI18_doll) C++14
84 / 100
 90 ms 17400 KB 
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include "doll.h"
// #include "grader.cpp"
using namespace std;
const int mxn = 1e6 + 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 1 ms 316 KB Output is correct
2 Correct 31 ms 6692 KB Output is correct
3 Correct 38 ms 7624 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 8 ms 1996 KB Output is correct
6 Correct 56 ms 10220 KB Output is correct
7 Runtime error 1 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 1 ms 316 KB Output is correct
2 Correct 31 ms 6692 KB Output is correct
3 Correct 38 ms 7624 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 8 ms 1996 KB Output is correct
6 Correct 56 ms 10220 KB Output is correct
7 Runtime error 1 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 1 ms 316 KB Output is correct
2 Correct 31 ms 6692 KB Output is correct
3 Correct 38 ms 7624 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 8 ms 1996 KB Output is correct
6 Correct 56 ms 10220 KB Output is correct
7 Runtime error 1 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 1 ms 340 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 316 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 312 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 48 ms 9892 KB Output is correct
3 Correct 77 ms 11632 KB Output is correct
4 Correct 83 ms 15624 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 48 ms 9892 KB Output is correct
3 Correct 77 ms 11632 KB Output is correct
4 Correct 83 ms 15624 KB Output is correct
5 Correct 88 ms 17400 KB Output is correct
6 Correct 86 ms 16792 KB Output is correct
7 Correct 87 ms 16908 KB Output is correct
8 Correct 90 ms 16684 KB Output is correct
9 Correct 67 ms 11708 KB Output is correct
10 Correct 85 ms 16336 KB Output is correct
11 Correct 84 ms 15984 KB Output is correct
12 Correct 80 ms 11948 KB Output is correct
13 Correct 50 ms 10416 KB Output is correct
14 Correct 69 ms 12524 KB Output is correct
15 Correct 70 ms 12676 KB Output is correct
16 Correct 3 ms 724 KB Output is correct
17 Correct 50 ms 10264 KB Output is correct
18 Correct 49 ms 10092 KB Output is correct
19 Correct 75 ms 11912 KB Output is correct
20 Correct 90 ms 16424 KB Output is correct
21 Correct 85 ms 15868 KB Output is correct
22 Correct 86 ms 15948 KB Output is correct