Submission #209713

#	Time	Username	Problem	Language	Result	Execution time	Memory
209713		Alexa2001	Shuffle (NOI19_shuffle)	C++17	52 / 100	18 ms	8564 KiB

shuffle

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

using namespace std;

const int Nmax = 1005;


int b, k, n, one, Nr;

vector<vector<int>> query[15], ans1, ans2, ans3, to0, W[15];
vector<int> cycle;

int marked[Nmax][Nmax], on_cycle[Nmax];
int marked1[Nmax], marked2[Nmax], val[Nmax];



void step1()
{
    vector<int> aux;
    vector<vector<int>> to1, to2;

    int i, j;
    for(i=1; i<=b; ++i)
    {
        aux.clear();
        for(j=i*k-k+1; j<=i*k; ++j)
            aux.push_back(j);

        to1.push_back(aux);
    }

    ans1 = query[1] = shuffle(to1);

    for(i=1; i<b; ++i)
    {
        aux.clear();
        for(j=i*k-k+2; j<=i*k+1; ++j)
            aux.push_back(j);
        to2.push_back(aux);
    }

    aux.clear();
    aux.push_back(1);
    for(i=n-k+2; i<=n; ++i) aux.push_back(i);
    to2.push_back(aux);

    ans2 = shuffle(to2);

    aux.clear();
    aux.push_back(1);
    for(i=k+2; i<=2*k; ++i) aux.push_back(i);

    to0 = to1;
    to1[0] = aux;
    to1[1] = to2[0];

    ans3 = shuffle(to1);

    for(auto it : ans1)
        for(auto x : it)
            for(auto y : it)
                marked[x][y] ++, marked1[x] = max(marked1[x], x!=y ? y : 0);

    for(auto it : ans2)
        for(auto x : it)
            for(auto y : it)
                marked[x][y] ++, marked2[x] = max(marked2[x], x!=y ? y : 0);

    for(i=1; i<=n; ++i)
    {
        bool ok = 1;
        for(j=1; ok && j<=n; ++j)
            if(i != j && marked[i][j] > 1)
                ok = 0;
        if(ok) on_cycle[i] = 1;
    }

    for(auto it : ans3)
        for(auto x : it)
            for(auto y : it)
                marked[x][y] ++;

    for(i=1; i<=n; ++i)
    {
        bool ok = 1;
        for(j=1; ok && j<=n; ++j)
            if(i != j && marked[i][j] > 1)
                ok = 0;
        if(ok) one = i;
    }

    cycle.push_back(one);

    while(cycle.size() < b)
    {
        for(i=1; i<=n; ++i)
            if(on_cycle[i] && marked1[cycle.back()] == marked2[i])
            {
                cycle.push_back(i);
                break;
            }
    }

    for(i=0; i<b; ++i) val[cycle[i]] = i * k + 1;
}

void divide(vector<vector<int>> &to)
{
    bool ok = 0;
    int i, j;
    for(auto it : to)
        if(it.size() > 1) ok = 1;

    if(!ok) return;

    vector<vector<int>> w;

    for(auto it : to)
    {
        int cat, rest;
        cat = it.size() / b;
        rest = it.size() % b;

        int id = 0;

        for(i=0; i<b; ++i)
        {
            vector<int> aux;

            for(j=0; j<cat; ++j)
                aux.push_back(it[id++]);

            if(i < rest) aux.push_back(it[id++]);

            w.push_back(aux);
        }
    }

    vector<vector<int>> q;

    for(i=0; i<b; ++i)
    {
        int rest;
        int C = w.size() / b, id;

        vector<int> aux;

        for(j=0, rest = i; j<b; ++j, rest = (rest+1) % b)
        {
            for(id = C * j + rest; id < C * (j+1); id += b)
                for(auto it : w[id])
                    aux.push_back(it);
        }

        q.push_back(aux);
    }

    W[++Nr] = q;
    query[++Nr] = shuffle(q);

    divide(w);
}

vector<int> solve6()
{
    W[Nr = 1] = to0;
    divide(to0);


    vector<int> where(1e6 + 5, -1);
    vector<int> who(n+1, 0), whoo(n+1, 0);


    int i;
    for(i=1; i<=Nr; ++i)
        for(auto it : query[i])
        {
            int rep;
            for(auto x : it)
                if(on_cycle[x]) rep = val[x] / k;

            for(auto x : it)
                who[x] = who[x] * b + rep;
        }


    for(i=1; i<=n; ++i)
        where[who[i]] = i;


    for(auto itt : W)
        for(auto it : itt)
        {
            int rep;
            for(auto x : it)
                if(x % k == 1) rep = x / k;

            for(auto x : it)
                whoo[x] = whoo[x] * b + rep;
        }

    vector<int> p(n);

    for(i=1; i<=n; ++i)
        p[i-1] = where[whoo[i]];

    return p;
}

vector<int> solve(int N, int B, int K, int Q, int ST)
{
    n = B * K;
    b = B;
    k = K;

    if(ST != 6) return vector<int> ();

    step1();
    return solve6();
}

Compilation message (stderr)

shuffle.cpp: In function 'void step1()':
shuffle.cpp:96:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(cycle.size() < b)
           ~~~~~~~~~~~~~^~~
shuffle.cpp: In function 'std::vector<int> solve6()':
shuffle.cpp:201:39: warning: 'rep' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 whoo[x] = whoo[x] * b + rep;
shuffle.cpp:185:37: warning: 'rep' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 who[x] = who[x] * b + rep;

• Subtask 1: 0 / 2
• Subtask 2: 0 / 3
• Subtask 3: 0 / 12
• Subtask 4: 0 / 16
• Subtask 5: 0 / 15
• Subtask 6: 52 / 52