oj.uz

Submission #771798

# Submission time Handle Problem Language Result Execution time Memory
771798 2023-07-03T09:32:29 Z Amylopectin Mechanical Doll (IOI18_doll) C++14
84 / 100
 123 ms 143308 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> 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 38 ms 70868 KB Output is correct
2 Correct 69 ms 76816 KB Output is correct
3 Correct 72 ms 77796 KB Output is correct
4 Correct 31 ms 70740 KB Output is correct
5 Correct 40 ms 72416 KB Output is correct
6 Correct 81 ms 80084 KB Output is correct
7 Runtime error 90 ms 143308 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 38 ms 70868 KB Output is correct
2 Correct 69 ms 76816 KB Output is correct
3 Correct 72 ms 77796 KB Output is correct
4 Correct 31 ms 70740 KB Output is correct
5 Correct 40 ms 72416 KB Output is correct
6 Correct 81 ms 80084 KB Output is correct
7 Runtime error 90 ms 143308 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 38 ms 70868 KB Output is correct
2 Correct 69 ms 76816 KB Output is correct
3 Correct 72 ms 77796 KB Output is correct
4 Correct 31 ms 70740 KB Output is correct
5 Correct 40 ms 72416 KB Output is correct
6 Correct 81 ms 80084 KB Output is correct
7 Runtime error 90 ms 143308 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 31 ms 70676 KB Output is correct
2 Correct 31 ms 70740 KB Output is correct
3 Correct 31 ms 70700 KB Output is correct
4 Correct 34 ms 70756 KB Output is correct
5 Correct 32 ms 70740 KB Output is correct
6 Correct 32 ms 70744 KB Output is correct
7 Correct 31 ms 70780 KB Output is correct
8 Correct 32 ms 70760 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 70780 KB Output is correct
2 Correct 80 ms 79600 KB Output is correct
3 Correct 103 ms 81332 KB Output is correct
4 Correct 112 ms 84652 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 70780 KB Output is correct
2 Correct 80 ms 79600 KB Output is correct
3 Correct 103 ms 81332 KB Output is correct
4 Correct 112 ms 84652 KB Output is correct
5 Correct 121 ms 86520 KB Output is correct
6 Correct 119 ms 85804 KB Output is correct
7 Correct 118 ms 85992 KB Output is correct
8 Correct 118 ms 85804 KB Output is correct
9 Correct 100 ms 81276 KB Output is correct
10 Correct 116 ms 85484 KB Output is correct
11 Correct 118 ms 85108 KB Output is correct
12 Correct 104 ms 81572 KB Output is correct
13 Correct 84 ms 80112 KB Output is correct
14 Correct 108 ms 82164 KB Output is correct
15 Correct 108 ms 82364 KB Output is correct
16 Correct 34 ms 71088 KB Output is correct
17 Correct 80 ms 79844 KB Output is correct
18 Correct 80 ms 79832 KB Output is correct
19 Correct 103 ms 81528 KB Output is correct
20 Correct 117 ms 85512 KB Output is correct
21 Correct 116 ms 85004 KB Output is correct
22 Correct 123 ms 85228 KB Output is correct