Submission #255471

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
255471	2020-08-01T05:42:49 Z	davitmarg	Mechanical Doll (IOI18_doll)	C++17	16 / 100	110 ms	21940 KB

doll

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;

const int N = 200005;

#ifndef  death
#include "doll.h"
#endif // ! death

#ifdef death
void answer(vector<int> c, vector<int> x, vector<int> y)
{
    for (int i = 0; i < c.size(); i++)
        cout << c[i] << " ";
    cout << endl;
    for (int i = 0; i < x.size(); i++)
        cout << x[i] << " : " << y[i] << endl;
}
#endif

int bitcount(int x)
{
    int res = 0;
    while (x)
    {
        res += x % 2;
        x /= 2;
    }
    return res;
}

int n, k;
vector<int> pos[N+N], p, X, Y,nxt;

int add()
{
    k++;
    X.push_back(0);
    Y.push_back(0);
    return k;
}

int han = 0;
void build(int st,int d,int val, int c, int x)
{
    int v = k;
    if (c)
    {
        int mx = (1 << (c + d)) - (1 << d);
        if (x + mx < han)
            X[v - 1] = -st;
        else
        {
            X[v - 1] = -add();
            build(st, d + 1, val, c - 1, x);
        }

        x += (1 << d);

        Y[v - 1] = -add();
        build(st, d + 1, val, c - 1, x);
    }
    else
    {
        int x1 = x-han;
        int x2 = x + (1 << d) - han;
        if (x1 >= 0)
            X[v - 1] = pos[val][pos[val].size() - 1 - x1];
        else
            X[v - 1] = -st;

        if (x2 >= 0)
            Y[v - 1] = pos[val][pos[val].size() - 1 - x2];
        else
            Y[v - 1] = -st;
    }
}

void solve(int val)
{
    if (pos[val].empty())
        return;
    if (pos[val].size() == 1)
    {
        nxt[val] = pos[val][0];
        return;
    }
   
    for(int i=0;i<30;i++)
        if ((1 << i) >= pos[val].size())
        {
            nxt[val] = -add();
            han = (1 << i) - pos[val].size();
            build(k, 0, val, i-1, 0);
            break;
        }
}

void create_circuit(int M, vector<int> A)
{
    n = M;
    p = A;
    p.PB(0);
    nxt.resize(n + 1);
    for (int i = p.size() - 2; i >= 0; i--)
        pos[p[i]].push_back(p[i+1]);
    for (int i = 1; i <= n; i++)
        solve(i);
    nxt[0] = p[0];
    answer(nxt, X, Y);
}

#ifdef death
int main()
{
    fastIO;
    int nn;
    vector<int> aa;
    cin >> nn >> nn;
    for (int i = 1; i <= nn; i++)
    {
        int x;
        cin >> x;
        aa.push_back(x);
    }

    create_circuit(nn, aa);

    return 0;
}
#endif

/*

1 5
1 1 1 1 1

*/

Compilation message

doll.cpp: In function 'void solve(int)':
doll.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         if ((1 << i) >= pos[val].size())
      |             ~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	9676 KB	Output is correct
2	Correct	54 ms	13660 KB	Output is correct
3	Correct	32 ms	13316 KB	Output is correct
4	Correct	8 ms	9676 KB	Output is correct
5	Correct	19 ms	10868 KB	Output is correct
6	Correct	63 ms	15272 KB	Output is correct
7	Correct	7 ms	9676 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	9676 KB	Output is correct
2	Correct	54 ms	13660 KB	Output is correct
3	Correct	32 ms	13316 KB	Output is correct
4	Correct	8 ms	9676 KB	Output is correct
5	Correct	19 ms	10868 KB	Output is correct
6	Correct	63 ms	15272 KB	Output is correct
7	Correct	7 ms	9676 KB	Output is correct
8	Correct	62 ms	16344 KB	Output is correct
9	Correct	68 ms	16648 KB	Output is correct
10	Correct	101 ms	20160 KB	Output is correct
11	Correct	7 ms	9676 KB	Output is correct
12	Correct	8 ms	9676 KB	Output is correct
13	Correct	8 ms	9676 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	9676 KB	Output is correct
2	Correct	54 ms	13660 KB	Output is correct
3	Correct	32 ms	13316 KB	Output is correct
4	Correct	8 ms	9676 KB	Output is correct
5	Correct	19 ms	10868 KB	Output is correct
6	Correct	63 ms	15272 KB	Output is correct
7	Correct	7 ms	9676 KB	Output is correct
8	Correct	62 ms	16344 KB	Output is correct
9	Correct	68 ms	16648 KB	Output is correct
10	Correct	101 ms	20160 KB	Output is correct
11	Correct	7 ms	9676 KB	Output is correct
12	Correct	8 ms	9676 KB	Output is correct
13	Correct	8 ms	9676 KB	Output is correct
14	Correct	110 ms	21940 KB	Output is correct
15	Correct	62 ms	16060 KB	Output is correct
16	Correct	90 ms	19108 KB	Output is correct
17	Correct	7 ms	9688 KB	Output is correct
18	Correct	8 ms	9676 KB	Output is correct
19	Correct	8 ms	9616 KB	Output is correct
20	Correct	104 ms	20672 KB	Output is correct
21	Correct	8 ms	9624 KB	Output is correct
22	Correct	7 ms	9676 KB	Output is correct