oj.uz

Submission #209538

# Submission time Handle Problem Language Result Execution time Memory
209538 2020-03-14T13:09:02 Z oolimry Shuffle (NOI19_shuffle) C++14
100 / 100
 124 ms 24056 KB 
#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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 376 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 16120 KB Output is correct
2 Correct 8 ms 2552 KB Output is correct
3 Correct 5 ms 1016 KB Output is correct
4 Correct 16 ms 3320 KB Output is correct
5 Correct 9 ms 4344 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4344 KB Output is correct
2 Correct 6 ms 1144 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 5 ms 888 KB Output is correct
5 Correct 7 ms 2860 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 24056 KB Output is correct
2 Correct 15 ms 2424 KB Output is correct
3 Correct 34 ms 6908 KB Output is correct
4 Correct 124 ms 24032 KB Output is correct
5 Correct 121 ms 24056 KB Output is correct

Subtask #6
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 31 ms 4216 KB Output is correct
4 Correct 78 ms 16120 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 79 ms 16120 KB Output is correct
7 Correct 9 ms 1528 KB Output is correct
8 Correct 9 ms 1656 KB Output is correct
9 Correct 8 ms 1144 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 8 ms 760 KB Output is correct
12 Correct 78 ms 16120 KB Output is correct
13 Correct 9 ms 760 KB Output is correct
14 Correct 11 ms 1656 KB Output is correct
15 Correct 13 ms 2424 KB Output is correct
16 Correct 79 ms 16096 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 60 ms 12536 KB Output is correct
19 Correct 13 ms 2424 KB Output is correct
20 Correct 8 ms 760 KB Output is correct