oj.uz

Submission #771831

# Submission time Handle Problem Language Result Execution time Memory
771831 2023-07-03T10:08:44 Z Amylopectin Mechanical Doll (IOI18_doll) C++14
100 / 100
 92 ms 18328 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
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 32 ms 6332 KB Output is correct
3 Correct 38 ms 7264 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 9472 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 32 ms 6332 KB Output is correct
3 Correct 38 ms 7264 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 9472 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 54 ms 11524 KB Output is correct
9 Correct 84 ms 14200 KB Output is correct
10 Correct 92 ms 18328 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 32 ms 6332 KB Output is correct
3 Correct 38 ms 7264 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 9472 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 54 ms 11524 KB Output is correct
9 Correct 84 ms 14200 KB Output is correct
10 Correct 92 ms 18328 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 89 ms 17816 KB Output is correct
15 Correct 73 ms 13348 KB Output is correct
16 Correct 90 ms 17568 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 91 ms 18020 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 316 KB Output is correct

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 0 ms 340 KB Output is correct
2 Correct 50 ms 9040 KB Output is correct
3 Correct 68 ms 10736 KB Output is correct
4 Correct 83 ms 14160 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 50 ms 9040 KB Output is correct
3 Correct 68 ms 10736 KB Output is correct
4 Correct 83 ms 14160 KB Output is correct
5 Correct 90 ms 15960 KB Output is correct
6 Correct 86 ms 15304 KB Output is correct
7 Correct 87 ms 15404 KB Output is correct
8 Correct 92 ms 15220 KB Output is correct
9 Correct 67 ms 10692 KB Output is correct
10 Correct 85 ms 14948 KB Output is correct
11 Correct 84 ms 14508 KB Output is correct
12 Correct 69 ms 10968 KB Output is correct
13 Correct 51 ms 9536 KB Output is correct
14 Correct 70 ms 11652 KB Output is correct
15 Correct 70 ms 11736 KB Output is correct
16 Correct 2 ms 724 KB Output is correct
17 Correct 48 ms 9336 KB Output is correct
18 Correct 48 ms 9168 KB Output is correct
19 Correct 67 ms 10988 KB Output is correct
20 Correct 88 ms 15020 KB Output is correct
21 Correct 85 ms 14560 KB Output is correct
22 Correct 83 ms 14508 KB Output is correct