oj.uz

Submission #248741

# Submission time Handle Problem Language Result Execution time Memory
248741 2020-07-13T09:35:58 Z SamAnd Shuffle (NOI19_shuffle) C++17
2 / 100
 3 ms 640 KB 
#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]);
                }
                else
                    assert(false);
            }
            ans.push_back(yans[0]);
        }
        return ans;
    }
}

/*
6 2 3 100 2
3 1 4 5 2 6
*/

Compilation message

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:131:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Wrong Answer. Returned result not of length 6.
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Wrong Answer. Returned result not of length 999.
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Wrong Answer. Returned result not of length 1000.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Wrong Answer. Returned result not of length 99.
2 Halted 0 ms 0 KB -