oj.uz

Submission #879647

# Submission time Handle Problem Language Result Execution time Memory
879647 2023-11-27T19:25:55 Z andrei_boaca Mechanical Doll (IOI18_doll) C++17
53 / 100
 129 ms 29632 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 added=0;
int build(int lg)
{
    if(lg==1)
        return INF;
    added+=lg%2;
    lg+=lg%2;
    int a=build(lg/2);
    int b=build(lg/2);
    s++;
    lft[s]=a;
    rgt[s]=b;
    return -s;
}
int plsmake()
{
    if(v.size()==1)
        return v[0];
    ll lg=v.size();
    added=0;
    int c=build(lg);
    vector<pii> ord;
    for(int i=1;i<=lg+added;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)
{
    C.resize(M+1);
    n=A.size();
    /*if(n==16)
    {
        C[0]=A[0];
        for(int i=1;i<A.size();i++)
            v.push_back(A[i]);
        v.push_back(0);
        int c=plsmake();
        for(int i=1;i<=M;i++)
            C[i]=c;
        for(int i=1;i<=s;i++)
        {
            X.push_back(lft[i]);
            Y.push_back(rgt[i]);
        }
        answer(C,X,Y);
        return;
    }*/
    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[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:69: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]
   69 |     for(int i=0;i<ord.size();i++)
      |                 ~^~~~~~~~~~~
doll.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         if(i+1<v.size())
      |            ~~~^~~~~~~~~
doll.cpp:81: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]
   81 |         if(i+1==ord.size())
      |            ~~~^~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int i=0;i<A.size();i++)
      |                 ~^~~~~~~~~
doll.cpp:121:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         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 8028 KB Output is correct
3 Correct 15 ms 7512 KB Output is correct
4 Correct 1 ms 3928 KB Output is correct
5 Correct 8 ms 4956 KB Output is correct
6 Correct 21 ms 9564 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 8028 KB Output is correct
3 Correct 15 ms 7512 KB Output is correct
4 Correct 1 ms 3928 KB Output is correct
5 Correct 8 ms 4956 KB Output is correct
6 Correct 21 ms 9564 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct
8 Correct 40 ms 14912 KB Output is correct
9 Correct 37 ms 15256 KB Output is correct
10 Correct 63 ms 18632 KB Output is correct
11 Correct 1 ms 5724 KB Output is correct
12 Correct 1 ms 5720 KB Output is correct
13 Correct 1 ms 5720 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 8028 KB Output is correct
3 Correct 15 ms 7512 KB Output is correct
4 Correct 1 ms 3928 KB Output is correct
5 Correct 8 ms 4956 KB Output is correct
6 Correct 21 ms 9564 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct
8 Correct 40 ms 14912 KB Output is correct
9 Correct 37 ms 15256 KB Output is correct
10 Correct 63 ms 18632 KB Output is correct
11 Correct 1 ms 5724 KB Output is correct
12 Correct 1 ms 5720 KB Output is correct
13 Correct 1 ms 5720 KB Output is correct
14 Correct 66 ms 20888 KB Output is correct
15 Correct 36 ms 14524 KB Output is correct
16 Correct 55 ms 17940 KB Output is correct
17 Correct 1 ms 5720 KB Output is correct
18 Correct 1 ms 6112 KB Output is correct
19 Correct 1 ms 5724 KB Output is correct
20 Correct 60 ms 19628 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 5724 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 1 ms 5724 KB Output is partially correct
2 Correct 51 ms 16004 KB Output is correct
3 Partially correct 105 ms 22272 KB Output is partially correct
4 Partially correct 105 ms 23084 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 5724 KB Output is partially correct
2 Correct 51 ms 16004 KB Output is correct
3 Partially correct 105 ms 22272 KB Output is partially correct
4 Partially correct 105 ms 23084 KB Output is partially correct
5 Partially correct 80 ms 23320 KB Output is partially correct
6 Partially correct 87 ms 20936 KB Output is partially correct
7 Partially correct 90 ms 20220 KB Output is partially correct
8 Partially correct 89 ms 27840 KB Output is partially correct
9 Partially correct 94 ms 21860 KB Output is partially correct
10 Partially correct 129 ms 29632 KB Output is partially correct
11 Partially correct 107 ms 28388 KB Output is partially correct
12 Partially correct 67 ms 20276 KB Output is partially correct
13 Partially correct 61 ms 19212 KB Output is partially correct
14 Partially correct 61 ms 18680 KB Output is partially correct
15 Partially correct 56 ms 18112 KB Output is partially correct
16 Partially correct 3 ms 6236 KB Output is partially correct
17 Partially correct 47 ms 17640 KB Output is partially correct
18 Partially correct 57 ms 17680 KB Output is partially correct
19 Partially correct 50 ms 18312 KB Output is partially correct
20 Partially correct 65 ms 21528 KB Output is partially correct
21 Partially correct 90 ms 26172 KB Output is partially correct
22 Partially correct 60 ms 20636 KB Output is partially correct