Submission #248811

#	Time	Username	Problem	Language	Result	Execution time	Memory
248811		SamAnd	Shuffle (NOI19_shuffle)	C++17	17 / 100	178 ms	384 KiB

shuffle

#include "shuffle.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
const int N = 1003;

int n, b, k;

vector<int> hat(vector<int> a, vector<int> b)
{
    vector<int> res;
    sort(all(a));
    sort(all(b));
    for (int i = 0; i < sz(a); ++i)
    {
        if (binary_search(all(b), a[i]))
            res.push_back(a[i]);
    }
    return res;
}

void tp(vector<int> v)
{
    for (int i = 0; i < v.size(); ++i)
        printf("%d ", v[i]);
    printf("\n");
}

int l[N], r[N];

vector<int> solve(int n, int b, int k, int Q, int ST)
{
    ::n = n;
    ::b = b;
    ::k = k;
    if (b == 2)
    {
        int ans1;
        vector<vector<vector<int> > > vvv, vvv0;
        for (int j = 0; j < 10; ++j)
        {
            vector<vector<int> > vv(b);
            bool z = false;
            for (int i = 1; i <= n; ++i)
            {
                if (j == 0)
                {
                    if (i <= n / 2)
                    {
                        l[i] = 1;
                        r[i] = n / 2;
                        vv[1].push_back(i);
                    }
                    else
                    {
                        l[i] = n / 2 + 1;
                        r[i] = n;
                        vv[0].push_back(i);
                    }
                }
                else
                {
                    int m = (l[i] + r[i]) / 2;
                    if ((r[i] - l[i] + 1) % 2 == 0)
                    {
                        if (i <= m)
                        {
                            r[i] = m;
                            vv[1].push_back(i);
                        }
                        else
                        {
                            l[i] = m + 1;
                            vv[0].push_back(i);
                        }
                    }
                    else
                    {
                        if (i < m)
                        {
                            if (!z)
                            {
                                r[i] = m - 1;
                                vv[1].push_back(i);
                            }
                            else
                            {
                                r[i] = m;
                                vv[1].push_back(i);
                            }
                        }
                        else if (i > m)
                        {
                            if (z)
                            {
                                l[i] = m;
                                vv[0].push_back(i);
                            }
                            else
                            {
                                l[i] = m + 1;
                                vv[0].push_back(i);
                            }
                        }
                        else
                        {
                            if (!z)
                            {
                                l[i] = m;
                                vv[0].push_back(i);
                            }
                            else
                            {
                                r[i] = m;
                                vv[1].push_back(i);
                            }
                            z ^= true;
                        }
                    }
                }
            }
            reverse(all(vv[0]));
            while (vv[1].size() < vv[0].size())
            {
                vv[1].push_back(vv[0].back());
                vv[0].pop_back();
            }
            while (vv[0].size() < vv[1].size())
            {
                vv[0].push_back(vv[1].back());
                vv[1].pop_back();
            }
            sort(all(vv[0]));
            sort(all(vv[1]));
            vvv.push_back(shuffle(vv));
            sort(all(vvv.back()[0]));
            sort(all(vvv.back()[1]));
            if (j == 0)
            {
                vector<vector<int> > u0, u1;
                swap(vv[0][0], vv[1][0]);
                u0 = shuffle(vv);
                swap(vv[0][0], vv[1][0]);
                swap(vv[0][1], vv[1][0]);
                u1 = shuffle(vv);
                swap(vv[0][1], vv[1][0]);

                int u00, u01;
                if (hat(u0[0], vvv.back()[0]).size() == 1)
                    u00 = hat(u0[0], vvv.back()[0])[0];
                else
                    u00 = hat(u0[1], vvv.back()[0])[0];
                if (hat(u0[0], vvv.back()[1]).size() == 1)
                    u01 = hat(u0[0], vvv.back()[1])[0];
                else
                    u01 = hat(u0[1], vvv.back()[1])[0];

                int u10, u11;
                if (hat(u1[0], vvv.back()[0]).size() == 1)
                    u10 = hat(u1[0], vvv.back()[0])[0];
                else
                    u10 = hat(u1[1], vvv.back()[0])[0];
                if (hat(u1[0], vvv.back()[1]).size() == 1)
                    u11 = hat(u1[0], vvv.back()[1])[0];
                else
                    u11 = hat(u1[1], vvv.back()[1])[0];

                if (u00 == u10 || u00 == u11)
                    ans1 = u00;
                else
                    ans1 = u01;
            }
            vvv0.push_back(vv);
            if (binary_search(all(vvv.back()[0]), ans1) != binary_search(all(vv[0]), 1))
                swap(vvv.back()[0], vvv.back()[1]);
        }
        vector<int> ans;
        for (int i = 1; i <= n; ++i)
        {
            vector<int> yans;
            for (int j = 1; j <= n; ++j)
                yans.push_back(j);
            for (int j = 0; j < 10; ++j)
            {
                if (binary_search(all(vvv0[j][1]), i))
                {
                    yans = hat(yans, vvv[j][1]);
                }
                else
                {
                    yans = hat(yans, vvv[j][0]);
                }
            }
            ans.push_back(yans[0]);
        }
        return ans;
    }
}

/*
20 2 10 12 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

6 2 3 100 2
1 2 3 4 5 6
14 2 7 12 5
14 2 3 10 5 6 7 8 9 4 11 12 13 1
*/

Compilation message (stderr)

shuffle.cpp: In function 'void tp(std::vector<int>)':
shuffle.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
shuffle.cpp: In function 'std::vector<int> solve(int, int, int, int, int)':
shuffle.cpp:202:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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