oj.uz

답안 #771811

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771811 2023-07-03T09:40:59 Z Amylopectin 자동 인형 (IOI18_doll) C++14
84 / 100
 100 ms 15912 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> 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 31 ms 6216 KB Output is correct
3 Correct 38 ms 7260 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 8 ms 1948 KB Output is correct
6 Correct 48 ms 9556 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 31 ms 6216 KB Output is correct
3 Correct 38 ms 7260 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 8 ms 1948 KB Output is correct
6 Correct 48 ms 9556 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 31 ms 6216 KB Output is correct
3 Correct 38 ms 7260 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 8 ms 1948 KB Output is correct
6 Correct 48 ms 9556 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 224 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 48 ms 9028 KB Output is correct
3 Correct 68 ms 10572 KB Output is correct
4 Correct 86 ms 14016 KB Output is correct

Subtask #6
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 48 ms 9028 KB Output is correct
3 Correct 68 ms 10572 KB Output is correct
4 Correct 86 ms 14016 KB Output is correct
5 Correct 88 ms 15912 KB Output is correct
6 Correct 90 ms 15220 KB Output is correct
7 Correct 87 ms 15276 KB Output is correct
8 Correct 100 ms 15092 KB Output is correct
9 Correct 67 ms 10640 KB Output is correct
10 Correct 84 ms 14800 KB Output is correct
11 Correct 87 ms 14420 KB Output is correct
12 Correct 68 ms 10868 KB Output is correct
13 Correct 54 ms 9652 KB Output is correct
14 Correct 70 ms 11520 KB Output is correct
15 Correct 70 ms 11624 KB Output is correct
16 Correct 3 ms 684 KB Output is correct
17 Correct 48 ms 9280 KB Output is correct
18 Correct 48 ms 9260 KB Output is correct
19 Correct 67 ms 10864 KB Output is correct
20 Correct 84 ms 14928 KB Output is correct
21 Correct 84 ms 14360 KB Output is correct
22 Correct 89 ms 14384 KB Output is correct