Submission #209538

#	Time	Username	Problem	Language	Result	Execution time	Memory
209538		oolimry	Shuffle (NOI19_shuffle)	C++14	100 / 100	124 ms	24056 KiB

shuffle

#include "shuffle.h"
#include <bits/stdc++.h>
using namespace std;


vector<int> solve(int N, int B, int K, int Q, int ST) {
    if(K == 2){
        vector<int> v;

        int arr[N];
        int adj[N][N];
        //int vis[N];
        int point1[N];
        int point2[N];
        for(int i = 0;i < N;i++){
            for(int j = 0;j < N;j++){
                adj[i][j] = 0;
            }
            arr[i] = 0;

        }
        vector<vector<int> > p;
        vector<int> pl;
        for(int i = 0;i < N;i++){

            pl.push_back(i+1);
            if(i % 2 == 1){
                p.push_back(pl);
                //cout << pl.size();
                pl.clear();
            }

        }

        p = shuffle(p);
        for(int i = 0;i < B;i++){
            for(int k = 0;k < K;k++){
                //cout << p[i][k] << " ";
            }
            //cout << "\n";
            int a = p[i][0];
            int b = p[i][1];
            a--;
            b--;
            adj[a][b] = 1;
            adj[b][a] = 1;
            point1[a] = b;
            point1[b] = a;
            //cout << a << " " << b << "\n";
        }
        p.clear();
        //vector<vector<int> > p;
        //vector<int> pl;
        for(int i = 1;i < N+1;i++){

            pl.push_back(i%N+1);
            if(i % 2 == 0){
                p.push_back(pl);
                //cout << pl.size();
                pl.clear();
            }

        }

        p = shuffle(p);
        for(int i = 0;i < B;i++){
            for(int k = 0;k < K;k++){
                //cout << p[i][k] << " ";
            }
            //cout << "\n";
            int a = p[i][0];
            int b = p[i][1];
            a--;
            b--;
            adj[a][b] = 1;
            adj[b][a] = 1;
            point2[a] = b;
            point2[b] = a;
            //cout << a << " " << b << "\n";
        }

        p.clear();

        for(int i = 0;i < B;i++){
            if(i == 0){

                pl.push_back(1);
                pl.push_back(2);
            }
            else{
                pl.push_back(2 + i);
                pl.push_back((N/2) + 1 + i);
            }
            p.push_back(pl);
            pl.clear();
        }

        p = shuffle(p);
        for(int i = 0;i < B;i++){
            for(int k = 0;k < K;k++){
                //cout << p[i][k] << " ";
            }
            //cout << "\n";
            int a = p[i][0];
            int b = p[i][1];
            a--;
            b--;
            if(adj[a][b]){
                arr[a]++;
                arr[b]++;
            }
        }


        p.clear();

        for(int i = 0;i < B;i++){
            if(i == 0){

                pl.push_back(1);
                pl.push_back(N);
            }
            else{
                pl.push_back(1 + i);
                pl.push_back((N/2)  + i);
            }
            p.push_back(pl);
            pl.clear();
        }

        p = shuffle(p);
        for(int i = 0;i < B;i++){
            for(int k = 0;k < K;k++){
                //cout << p[i][k] << " ";
            }
            //cout << "\n";
            int a = p[i][0];
            int b = p[i][1];
            a--;
            b--;
            if(adj[a][b]){
                arr[a]++;
                arr[b]++;
            }
        }
        int s = 0;

        for(int i = 0;i < N;i++){
           // cout << arr[i] << " ";
            if(arr[i] == 2) s = i;
        }

        //cout << s << "\n";

        for(int i = 0;i < N;i++){
            v.push_back(s + 1);
            if(i % 2 == 0) s = point1[s];
            else s = point2[s];
        }
        for(int i = 0;i < v.size();i++){
            //cout << v[i] << " ";
        }
        return v;
    }
    vector<int> v;
    vector< vector<int> > table;
    vector< vector<int> > res;
    vector<int> row;


    set<int> anchors; ///1 indexed
    vector<int> ancherorder;
    int anchor1 = -12321;
    map<int,int> connect;

    set<int> r1[N]; ///0 indexed
    int result1[B][K];

    ///pt. 1

    ///-------------------------------------------------------------------------///

    ///1: create
    for(int i = 0;i < B;i++){
        for(int j = 0;j < K;j++){
            row.push_back(i * K + j + 1);
            //cout << i * B + j + 1 << "\n";
        }
        table.push_back(row);
        row.clear();
    }

    res = shuffle(table);
/*
    ///1: print
    for(int i = 0;i < B;i++){
        for(int j = 0;j < K;j++){
            cout << res[i][j] << " ";
        }
        cout << "\n";
    }
    */
    ///1: analyse
    for(int i = 0;i < B;i++){
        for(int j = 0;j < K;j++){
            for(int k = 0;k < K;k++){
                if(k == j) continue;
                r1[res[i][j]-1].insert(res[i][k]-1);
            }
        }vector<int> before[N]; ///fingerprints
    vector<int> after[N]; ///fingerprints
    }

    ///2: create
    table.clear();
    for(int i = 0;i < B;i++){
        for(int j = 0;j < K;j++){
            row.push_back((i * K + j + 1) % N + 1);
            //cout << (i * K + j + 2) % N << "\n";
        }
        table.push_back(row);
        row.clear();
    }

    res = shuffle(table);

    ///2: print
    /*
    for(int i = 0;i < B;i++){
        for(int j = 0;j < K;j++){
            cout << res[i][j] << " ";
        }
        cout << "\n";
    }
    */
    ///2: analyse: find the anchors - 1, 1 + K, 1 + 2K, ...
    for(int i = 0;i < B;i++){
        for(int j = 0;j < K;j++){
            int c = 0;
            for(int k = 0;k < K;k++){
                if(k == j) continue;
                if(r1[res[i][j] - 1].find(res[i][k]-1) != r1[res[i][j] - 1].end()) c++;
            }
            if(c == 0){
                //cout << res[i][j] << "\n";
                anchors.insert(res[i][j]);
            }
        }
    }
    ///connect fat to anchor
    for(int i = 0;i < B;i++){
        int maxV = 0;///use max value as a key for the entire set of elements
        int an = 0;
        for(int j = 0;j < K;j++){
            if(anchors.find(res[i][j]) == anchors.end()){
                maxV = max(maxV,res[i][j]);
            }
            else{
                an = res[i][j];
            }
        }
        connect[maxV] = an;
        //cout << maxV << " " << an << "\n";
    }

    ///connect anchor to fat;
    for(set<int>::iterator it = anchors.begin();it != anchors.end();it++){
        int an = *it;
        int maxV = 0; ///use max value as a key for the entire set of elements
        for(set<int>::iterator it2 = r1[an-1].begin();it2 != r1[an-1].end();it2++){
            maxV = max(maxV,*it2+1);
        }
        connect[an] = maxV;
        //cout << an << " " << maxV << "\n";
    }

    ///3: create


    table.clear();
    for(int i = 0;i < B;i++){
        for(int j = 0;j < K;j++){
            row.push_back(i * K + j + 1);
        }
        table.push_back(row);
        row.clear();


    }
    int x = table[1][1];
    table[1][1] = table[0][0];
    table[0][0] = x;

    res = shuffle(table);

    for(int i = 0;i < B;i++){
        for(int j = 0;j < K;j++){
            int x = res[i][j];
            bool can = true;
            for(int k = 0;k < K;k++){

                if(r1[x-1].find(res[i][k]-1) != r1[x-1].end()){
                    can = false;
                    break;
                }
            }
            if(can){
                if(anchors.find(x) != anchors.end()){
                    anchor1 = x;
                    break;
                }
            }
        }

    }
    int a = anchor1;
    while(true){
        //cout << a << "\n";
        if(anchors.find(a) != anchors.end()) ancherorder.push_back(a);
        a = connect[a];
        if(a == anchor1) break;
    }



    ///find other anchors


    ///-------------------------------------------------------------------------///

    ///pt 2.


    ///-------------------------------------------------------------------------///

    vector<int> before[N]; ///fingerprints
    vector<int> after[N]; ///fingerprints
    map<int,int> anchorno;
    for(int i = 0;i < ancherorder.size();i++){
        anchorno[ancherorder[i]] = i;
        //cout << ancherorder[i] << "\n";
    }
    int ftS = 1;
    int S = 0; ///S = logB(N-B)
    while(ftS < N){
        ftS *= B;
        S++;
    }
    //cout << S << "\n";


    for(int i = 0;i < K;i++){
        vector<int> base;
        int c = i;
        for(int j = 0;j < S;j++){
            base.push_back(c % B);
            c /= B;
        }
        reverse(base.begin(),base.end());

        for(int j = 0;j < B;j++){
            for(int k = 0;k < S;k++){
                before[j * K + i].push_back((base[k] + j) % B);
            }
        }


        //cout << "\n";

    }


    for(int i = 0;i < ancherorder.size();i++){
        int an = ancherorder[i];
        for(set<int>::iterator it= r1[an-1].begin();it != r1[an-1].end();it++){
            int x = *it;
            after[x].push_back(i);
        }
        after[an-1].push_back(i);
    }

    for(int q = 1;q < S;q++){
        table.clear();
        for(int i = 0;i < B;i++){
            vector<int> v;
            table.push_back(v);
        }
        for(int i = 0;i < N;i++){
            int o = before[i][q];
            table[o].push_back(i+1);
        }
        res = shuffle(table);
        for(int i = 0;i < B;i++){
            int an = 0;
            for(int j = 0;j < K;j++){
                int x = res[i][j];
                if(anchors.find(x) != anchors.end()){
                    an = x;
                    break;
                }
            }

            int anno = anchorno[an];
            //cout << an << " " << anno << "\n";
            for(int j = 0;j < K;j++){
                int x = res[i][j];
                after[x-1].push_back(anno);
            }
        }
    }


    vector<int> ans;

    int be[N];
    int af[N];

    for(int i = 0;i < N;i++){
        int c = 0;
        for(int j = 0;j < before[i].size();j++){
            c *= B;
            c += before[i][j];
        }
        be[i] = c;
        c = 0;
        for(int j = 0;j < after[i].size();j++){
            c *= B;
            c += after[i][j];
        }
        af[i] = c;
    }


    map<int,int> aftM;

    for(int i = 0;i < N;i++){
        aftM[af[i]] = i;
    }

    for(int i = 0;i < N;i++){
        ans.push_back(aftM[be[i]] + 1);
    }



    ///-------------------------------------------------------------------------///

    return ans;
}

Compilation message (stderr)

shuffle.cpp: In function 'std::vector<int> solve(int, int, int, int, int)':
shuffle.cpp:160:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i < v.size();i++){
                       ~~^~~~~~~~~~
shuffle.cpp:339:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < ancherorder.size();i++){
                   ~~^~~~~~~~~~~~~~~~~~~~
shuffle.cpp:373:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < ancherorder.size();i++){
                   ~~^~~~~~~~~~~~~~~~~~~~
shuffle.cpp:420:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < before[i].size();j++){
                       ~~^~~~~~~~~~~~~~~~~~
shuffle.cpp:426:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < after[i].size();j++){
                       ~~^~~~~~~~~~~~~~~~~
shuffle.cpp:177:9: warning: unused variable 'result1' [-Wunused-variable]
     int result1[B][K];
         ^~~~~~~

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