oj.uz

답안 #879641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
879641 2023-11-27T19:16:03 Z andrei_boaca 자동 인형 (IOI18_doll) C++17
37 / 100
 164 ms 262144 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)
    {
        vector<int> v;
        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:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int i=1;i<A.size();i++)
      |                     ~^~~~~~~~~
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
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3676 KB Output is correct
2 Correct 18 ms 8028 KB Output is correct
3 Correct 14 ms 7512 KB Output is correct
4 Runtime error 164 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3676 KB Output is correct
2 Correct 18 ms 8028 KB Output is correct
3 Correct 14 ms 7512 KB Output is correct
4 Runtime error 164 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3676 KB Output is correct
2 Correct 18 ms 8028 KB Output is correct
3 Correct 14 ms 7512 KB Output is correct
4 Runtime error 164 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 159 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 5724 KB Output is partially correct
2 Correct 53 ms 16088 KB Output is correct
3 Partially correct 101 ms 22428 KB Output is partially correct
4 Partially correct 104 ms 23028 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 5724 KB Output is partially correct
2 Correct 53 ms 16088 KB Output is correct
3 Partially correct 101 ms 22428 KB Output is partially correct
4 Partially correct 104 ms 23028 KB Output is partially correct
5 Partially correct 80 ms 23572 KB Output is partially correct
6 Partially correct 85 ms 27172 KB Output is partially correct
7 Partially correct 89 ms 26572 KB Output is partially correct
8 Partially correct 85 ms 27764 KB Output is partially correct
9 Partially correct 94 ms 22044 KB Output is partially correct
10 Partially correct 122 ms 29748 KB Output is partially correct
11 Partially correct 107 ms 28348 KB Output is partially correct
12 Partially correct 65 ms 20304 KB Output is partially correct
13 Partially correct 55 ms 19220 KB Output is partially correct
14 Partially correct 54 ms 18784 KB Output is partially correct
15 Partially correct 53 ms 17948 KB Output is partially correct
16 Partially correct 3 ms 6232 KB Output is partially correct
17 Partially correct 47 ms 17492 KB Output is partially correct
18 Partially correct 56 ms 17660 KB Output is partially correct
19 Partially correct 50 ms 18276 KB Output is partially correct
20 Partially correct 66 ms 21324 KB Output is partially correct
21 Partially correct 93 ms 26076 KB Output is partially correct
22 Partially correct 65 ms 20696 KB Output is partially correct