oj.uz

Submission #771816

# Submission time Handle Problem Language Result Execution time Memory
771816 2023-07-03T09:47:45 Z Amylopectin Mechanical Doll (IOI18_doll) C++14
0 / 100
 1 ms 340 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

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 224 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong motion
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB wrong motion
2 Halted 0 ms 0 KB -