Submission #248743

#	Time	Username	Problem	Language	Result	Execution time	Memory
248743		SamAnd	Shuffle (NOI19_shuffle)	C++17	2 / 100	3 ms	640 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");
}

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);
            for (int i = 1; i <= n; ++i)
            {
                if ((i & (1 << j)))
                    vv[1].push_back(i);
                else
                    vv[0].push_back(i);
            }
            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 == u01)
                    ans1 = u00;
                else if (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 if (binary_search(all(vvv0[j][0]), i))
                {
                    yans = hat(yans, vvv[j][0]);
                }
            }
            ans.push_back(yans[0]);
        }
        return ans;
    }
}

/*
10 2 5 100 2
1 2 3 4 5 6 7 8 9 10
*/

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:87:21: warning: variable 'u10' set but not used [-Wunused-but-set-variable]
                 int u10, u11;
                     ^~~
shuffle.cpp:129: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: 0 / 15
• Subtask 6: 0 / 52