oj.uz

Submission #879603

# Submission time Handle Problem Language Result Execution time Memory
879603 2023-11-27T17:45:47 Z andrei_boaca Mechanical Doll (IOI18_doll) C++17
53 / 100
 122 ms 29776 KB 
#include "doll.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n;
const int INF=1e9;
vector<int> vecini[100005];
vector<int> C,X,Y;
vector<int> v;
int lft[5000005],rgt[5000005];
int s;
int state[5000005];
int build(int st,int dr)
{
    if(st==dr)
        return INF;
    ll lg=dr-st+1;
    if(__builtin_popcount(lg)==1)
    {
        ll mij=(st+dr)/2;
        ll a=build(st,mij);
        ll b=build(mij+1,dr);
        s++;
        lft[s]=a;
        rgt[s]=b;
        return -s;
    }
    ll lsb=(lg&(-lg));
    ll poz=dr-lsb;
    ll a=build(st,poz);
    ll b=build(poz+1,dr);
    s++;
    lft[s]=a;
    rgt[s]=b;
    return -s;
}
int plsmake()
{
    if(v.size()==1)
        return v[0];
    ll lg=v.size();
    while(__builtin_popcount(lg)>1)
        lg++;
    int c=build(0,lg-1);
    vector<pii> ord;
    for(int i=1;i<=lg;i++)
    {
        int nod=c;
        while(true)
        {
            nod=abs(nod);
            if(state[nod]==0)
            {
                if(lft[nod]==INF)
                {
                    ord.push_back({nod,0});
                    state[nod]^=1;
                    break;
                }
                state[nod]=1;
                nod=lft[nod];
                continue;
            }
            else
            {
                if(rgt[nod]==INF)
                {
                    ord.push_back({nod,1});
                    state[nod]^=1;
                    break;
                }
                state[nod]=0;
                nod=rgt[nod];
                continue;
            }
        }
    }
    for(int i=0;i<ord.size();i++)
    {
        int who=ord[i].first;
        int dir=ord[i].second;
        if(i+1<v.size())
        {
            if(dir==0)
                lft[who]=v[i];
            else
                rgt[who]=v[i];
            continue;
        }
        if(i+1==ord.size())
        {
            if(dir==0)
                lft[who]=v.back();
            else
                rgt[who]=v.back();
            continue;
        }
        if(dir==0)
            lft[who]=c;
        else
            rgt[who]=c;
    }
    return c;
}
void create_circuit(int M, std::vector<int> A)
{
    n=A.size();
    for(int i=0;i<A.size();i++)
    {
        int x=A[i];
        int nxt=0;
        if(i+1<A.size())
            nxt=A[i+1];
        vecini[x].push_back(nxt);
    }
    C.resize(M+1);
    C[0]=A[0];
    for(int i=1;i<=M;i++)
    {
        if(vecini[i].empty())
        {
            C[i]=0;
            continue;
        }
        else
        {
            v=vecini[i];
            C[i]=plsmake();
        }
    }
    for(int i=1;i<=s;i++)
    {
        X.push_back(lft[i]);
        Y.push_back(rgt[i]);
    }
    /*for(int i=0;i<C.size();i++)
        cout<<C[i]<<' ';
    cout<<'\n';
    for(int i=1;i<=s;i++)
        cout<<-i<<' '<<X[i-1]<<' '<<Y[i-1]<<'\n';*/
    answer(C,X,Y);
}

Compilation message

doll.cpp: In function 'int plsmake()':
doll.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=0;i<ord.size();i++)
      |                 ~^~~~~~~~~~~
doll.cpp:84:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         if(i+1<v.size())
      |            ~~~^~~~~~~~~
doll.cpp:92:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         if(i+1==ord.size())
      |            ~~~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i=0;i<A.size();i++)
      |                 ~^~~~~~~~~
doll.cpp:114:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         if(i+1<A.size())
      |            ~~~^~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 18 ms 8024 KB Output is correct
3 Correct 14 ms 7516 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 8 ms 4956 KB Output is correct
6 Correct 21 ms 9560 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 18 ms 8024 KB Output is correct
3 Correct 14 ms 7516 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 8 ms 4956 KB Output is correct
6 Correct 21 ms 9560 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct
8 Correct 43 ms 14864 KB Output is correct
9 Correct 37 ms 15256 KB Output is correct
10 Correct 60 ms 18632 KB Output is correct
11 Correct 1 ms 5720 KB Output is correct
12 Correct 1 ms 5724 KB Output is correct
13 Correct 1 ms 5912 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 18 ms 8024 KB Output is correct
3 Correct 14 ms 7516 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 8 ms 4956 KB Output is correct
6 Correct 21 ms 9560 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct
8 Correct 43 ms 14864 KB Output is correct
9 Correct 37 ms 15256 KB Output is correct
10 Correct 60 ms 18632 KB Output is correct
11 Correct 1 ms 5720 KB Output is correct
12 Correct 1 ms 5724 KB Output is correct
13 Correct 1 ms 5912 KB Output is correct
14 Correct 67 ms 20880 KB Output is correct
15 Correct 36 ms 14400 KB Output is correct
16 Correct 55 ms 18064 KB Output is correct
17 Correct 2 ms 6132 KB Output is correct
18 Correct 1 ms 5724 KB Output is correct
19 Correct 1 ms 5724 KB Output is correct
20 Correct 61 ms 19536 KB Output is correct
21 Correct 1 ms 5724 KB Output is correct
22 Correct 1 ms 5724 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 5720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 5724 KB Output is partially correct
2 Correct 51 ms 15888 KB Output is correct
3 Partially correct 100 ms 22160 KB Output is partially correct
4 Partially correct 102 ms 23084 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 5724 KB Output is partially correct
2 Correct 51 ms 15888 KB Output is correct
3 Partially correct 100 ms 22160 KB Output is partially correct
4 Partially correct 102 ms 23084 KB Output is partially correct
5 Partially correct 78 ms 23576 KB Output is partially correct
6 Partially correct 86 ms 27000 KB Output is partially correct
7 Partially correct 82 ms 26616 KB Output is partially correct
8 Partially correct 85 ms 27844 KB Output is partially correct
9 Partially correct 93 ms 22016 KB Output is partially correct
10 Partially correct 122 ms 29776 KB Output is partially correct
11 Partially correct 106 ms 29096 KB Output is partially correct
12 Partially correct 71 ms 20288 KB Output is partially correct
13 Partially correct 55 ms 19212 KB Output is partially correct
14 Partially correct 53 ms 18804 KB Output is partially correct
15 Partially correct 54 ms 18204 KB Output is partially correct
16 Partially correct 3 ms 6236 KB Output is partially correct
17 Partially correct 47 ms 17588 KB Output is partially correct
18 Partially correct 59 ms 17652 KB Output is partially correct
19 Partially correct 58 ms 18404 KB Output is partially correct
20 Partially correct 64 ms 21536 KB Output is partially correct
21 Partially correct 96 ms 26176 KB Output is partially correct
22 Partially correct 60 ms 20712 KB Output is partially correct