Submission #197177

#	Time	Username	Problem	Language	Result	Execution time	Memory
197177		stefdasca	Mechanical Doll (IOI18_doll)	C++14	2 / 100	1085 ms	12704 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>

using namespace std;

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

bool can[200002], canb[200002];

int ord[200002];
bool state[200002];
int nxt;
void dfs(int nod, int rem)
{
    if(rem == 0)
        return;
    --rem;
    if(rem)
    {
        ++nxt;
        can[-ord[nod]] = 0;
        adja[-ord[nod]] = ord[nxt];
        dfs(nxt, rem/2 + rem%2);
    }
    if(rem >= 2)
    {
        ++nxt;
        adjb[-ord[nod]] = ord[nxt];
        canb[-ord[nod]] = 0;
        dfs(nxt, rem / 2);
    }
}
void dfs2(int nod, int val)
{
    if(state[nod] == 0)
    {
        state[nod] = 1;
        if(!adja[nod])
        {
            adja[nod] = val;
            return;
        }
        else
            dfs2(-adja[nod], val);
    }
    else
    {
        state[nod] = 0;
        if(!adjb[nod])
        {
            adjb[nod] = val;
            return;
        }
        else
            dfs2(-adjb[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 = fi + 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 <= 200001; ++i)
        can[i] = canb[i] = 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 (stderr)

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

• Subtask 1: 2 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56