Submission #255248

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
255248	2020-07-31T16:06:58 Z	davitmarg	Mechanical Doll (IOI18_doll)	C++17	6 / 100	103 ms	15472 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], p, X, Y,nxt;

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

int build(int d,int val, int cnt, int x)
{
    int v = k;
    if (cnt > 1)
    {
        X[v - 1] = -add();
        build(d + 1, val, cnt / 2, x);
        Y[v - 1] = -add();
        return build(d + 1, val, cnt / 2, x + (1 << d));
    }
    else
    {
        int x1 = x;
        int x2 = x + (1 << d);
        X[v - 1] = pos[val][pos[val].size() - 1 - x1];
        if (x2 == (1 << (d + 1)) - 1)
            return v;
        Y[v - 1] = pos[val][pos[val].size() - 1 - x2];
    }
    return 0;
}

void solve(int val)
{
    if (pos[val].empty())
        return;
    if (pos[val].size() == 1)
    {
        nxt[val] = pos[val][0];
        return;
    }
    int last = -1;
    for (int I = 60; I >= 0; I--)
    {
        int i = I / 2;
        if ((1 << i) - 1 > pos[val].size() || (1 << i) - 1 == pos[val].size())
            continue;

        if (last == -1)
            nxt[val] = -add();
        else
            Y[last - 1] = -add();

        if ((1 << i) == pos[val].size())
        {
            Y[build(0, val, (1 << i)/2, 0) - 1] = pos[val][0];
            break;
        }
        last = build(0, val, (1 << i)/2, 0);
        for (int j = 1; j < (1 << i); j++)
            pos[val].pop_back();
    }
}

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:106:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         if ((1 << i) - 1 > pos[val].size() || (1 << i) - 1 == pos[val].size())
      |             ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
doll.cpp:106:60: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         if ((1 << i) - 1 > pos[val].size() || (1 << i) - 1 == pos[val].size())
      |                                               ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
doll.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         if ((1 << i) == pos[val].size())
      |             ~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4940 KB	Output is correct
2	Correct	37 ms	8884 KB	Output is correct
3	Correct	30 ms	8652 KB	Output is correct
4	Correct	5 ms	4940 KB	Output is correct
5	Correct	20 ms	6092 KB	Output is correct
6	Correct	44 ms	10616 KB	Output is correct
7	Correct	4 ms	4940 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4940 KB	Output is correct
2	Correct	37 ms	8884 KB	Output is correct
3	Correct	30 ms	8652 KB	Output is correct
4	Correct	5 ms	4940 KB	Output is correct
5	Correct	20 ms	6092 KB	Output is correct
6	Correct	44 ms	10616 KB	Output is correct
7	Correct	4 ms	4940 KB	Output is correct
8	Correct	68 ms	11640 KB	Output is correct
9	Correct	64 ms	12032 KB	Output is correct
10	Correct	100 ms	15472 KB	Output is correct
11	Correct	5 ms	4940 KB	Output is correct
12	Correct	5 ms	4892 KB	Output is correct
13	Correct	4 ms	4940 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4940 KB	Output is correct
2	Correct	37 ms	8884 KB	Output is correct
3	Correct	30 ms	8652 KB	Output is correct
4	Correct	5 ms	4940 KB	Output is correct
5	Correct	20 ms	6092 KB	Output is correct
6	Correct	44 ms	10616 KB	Output is correct
7	Correct	4 ms	4940 KB	Output is correct
8	Correct	68 ms	11640 KB	Output is correct
9	Correct	64 ms	12032 KB	Output is correct
10	Correct	100 ms	15472 KB	Output is correct
11	Correct	5 ms	4940 KB	Output is correct
12	Correct	5 ms	4892 KB	Output is correct
13	Correct	4 ms	4940 KB	Output is correct
14	Incorrect	103 ms	14704 KB	wrong motion
15	Halted	0 ms	0 KB	-