oj.uz

Submission #197215

# Submission time Handle Problem Language Result Execution time Memory
197215 2020-01-19T16:50:28 Z stefdasca Mechanical Doll (IOI18_doll) C++14
6 / 100
 1000 ms 11760 KB 
 #include "doll.h"
#include<bits/stdc++.h>

using namespace std;

vector<int> adj[100002];
int adja[200002], adjb[200002];

int ord[200002];
bool state[200002];
int nxt;
void dfs(int nod, int rem)
{
    if(rem == 0)
        return;
    --rem;
    if(rem)
    {
        ++nxt;
        adja[-ord[nod]] = ord[nxt];
        dfs(nxt, rem/2 + rem%2);
    }
    if(rem >= 2)
    {
        ++nxt;
        adjb[-ord[nod]] = ord[nxt];
        dfs(nxt, rem / 2);
    }
}
void dfs2(int nod, int val)
{
    if(state[-ord[nod]] == 0)
    {
        state[-ord[nod]] = 1;
        if(!adja[-ord[nod]])
        {
            adja[-ord[nod]] = val;
            return;
        }
        else
            dfs2(-adja[-ord[nod]], val);
    }
    else
    {
        state[-ord[nod]] = 0;
        if(!adjb[-ord[nod]])
        {
            adjb[-ord[nod]] = val;
            return;
        }
        else
            dfs2(-adjb[-ord[nod]], val);
    }
}
void build(int nod, int fi)
{
    for(int i = fi + 1; i < fi + adj[nod].size(); ++i)
        ord[i - fi] = i * (-1);
    nxt = 1;
    dfs(1, adj[nod].size() - 1);
    for(int i = 0; i < adj[nod].size(); ++i)
        dfs2(1, adj[nod][i]);

}
void create_circuit(int M, vector<int> A)
{
    int N = A.size();
    vector<int> C(M + 1);
    C[0] = A[0];
    for(int i = 0; i < A.size(); ++i)
    {
        if(i + 1 == A.size())
            adj[A[i]].push_back(0);
        else
            adj[A[i]].push_back(A[i+1]);
    }
    int sw = 0;
    for(int i = 1; i <= M; ++i)
    {
        if(adj[i].size() == 0)
            C[i] = 0;
        else
            if(adj[i].size() == 1)
                C[i] = adj[i][0];
            else
            {
                C[i] = -(sw + 1);
                build(i, sw);
                sw += adj[i].size() - 1;
            }
    }
    vector<int> X(sw), Y(sw);
    for(int k = 0; k < sw; ++k)
    {
        X[k] = adja[k + 1];
        Y[k] = adjb[k + 1];
    }
 //   for(int i = 0; i <= M; ++i)
  //      cout << C[i] << " ";
  //  cout << '\n';
  //  for(int k = 0; k < sw; ++k)
   //     cout << X[k] << " " << Y[k] << '\n';
    answer(C, X, Y);
}
/*
int main()
{
    int m, n;
    cin >> m >> n;
    vector<int> poz;
    for(int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        poz.push_back(x);
    }
    create_circuit(m, poz);
    return 0;
}
*/

Compilation message

doll.cpp: In function 'void build(int, int)':
doll.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = fi + 1; i < fi + adj[nod].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~
doll.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 0; i < adj[nod].size(); ++i)
      |                    ~~^~~~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < A.size(); ++i)
      |                    ~~^~~~~~~~~~
doll.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         if(i + 1 == A.size())
      |            ~~~~~~^~~~~~~~~~~
doll.cpp:67:9: warning: unused variable 'N' [-Wunused-variable]
   67 |     int N = A.size();
      |         ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 57 ms 6328 KB Output is correct
3 Correct 26 ms 5964 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 43 ms 7652 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 57 ms 6328 KB Output is correct
3 Correct 26 ms 5964 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 43 ms 7652 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 69 ms 8536 KB Output is correct
9 Correct 97 ms 8900 KB Output is correct
10 Correct 108 ms 11760 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 3 ms 2552 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 57 ms 6328 KB Output is correct
3 Correct 26 ms 5964 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 13 ms 3788 KB Output is correct
6 Correct 43 ms 7652 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 69 ms 8536 KB Output is correct
9 Correct 97 ms 8900 KB Output is correct
10 Correct 108 ms 11760 KB Output is correct
11 Correct 3 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 3 ms 2552 KB Output is correct
14 Execution timed out 1076 ms 6500 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 2636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2636 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2636 KB state 'Y'
2 Halted 0 ms 0 KB -