Submission #1204416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204416		loom	Shuffle (NOI19_shuffle)	C++20	2 / 100	4 ms	584 KiB

shuffle

#include "shuffle.h"
#include<bits/stdc++.h>
using namespace std;
#define inf 5e18
#define nl '\n'
#define vi vector<int>
#define vvi vector<vi>

int n, b, k;

vector<int> solve1(){
   vvi qry1(b), qry2(b);
   vvi res1, res2, res3, res4;
   vi p1(n+1), p2(n+1), p3(n+1), p4(n+1);

   for(int i=2, j=0; i<=n; i+=2, j++) qry1[j] = {i-1, i};
   res1 = shuffle(qry1);
   for(auto &v : res1){
      p1[v[0]] = v[1];
      p1[v[1]] = v[0];
   }

   for(int i=3, j=0; i<=n; i+=2, j++) qry2[j] = {i-1, i};
   qry2[b-1] = {1, n};
   res2 = shuffle(qry2);
   for(auto &v : res2){
      p2[v[0]] = v[1];
      p2[v[1]] = v[0];
   }

   swap(qry1[0][1], qry1[1][1]);
   res3 = shuffle(qry1);
   for(auto &v : res3){
      p3[v[0]] = v[1];
      p3[v[1]] = v[0];
   }

   swap(qry2[0][1], qry2[1][1]);
   res4 = shuffle(qry2);
   for(auto &v : res4){
      p4[v[0]] = v[1];
      p4[v[1]] = v[0];
   }

   vi ans(n+1);
   for(int i=1; i<=n; i++){
      if(p1[i] != p3[i] and p2[i] == p4[i]) ans[1] = i;
   }

   for(int i=1; i+2<=n; i+=2){
      int x = p1[ans[i]];
      ans[i+1] = x;
      ans[i+2] = p2[x];
   }

   ans.erase(ans.begin());
   return ans;
}

vector<int> solve2(){
   vvi qry1(b), qry2(b);
   vvi res1, res2, res3;
   vi box1(n+1), box2(n+1), box3(n+1);

   for(int i=1; i<=n; i++) qry1[(i-1)/k].push_back(i);
   res1 = shuffle(qry1);
   for(int i=0; i<b; i++){
      for(int x : res1[i]){
         box1[x] = i;
      }
   }

   for(int i=2; i<=n; i++) qry2[(i-2)/k].push_back(i);
   qry2[b-1].push_back(1);
   res2 = shuffle(qry2);
   for(int i=0; i<b; i++){
      for(int x : res2[i]){
         box2[x] = i;
      }
   }

   for(int i=1; i<k; i++) swap(qry1[0][i], qry1[1][i-1]);
   res3 = shuffle(qry1);
   for(int i=0; i<b; i++){
      for(int x : res3[i]){
         box3[x] = i;
      }
   }

   vi ans(n+1);
   for(int i=1; i<=n; i++){
      int tf = 1;
      for(int j : res1[box1[i]]){
         if(i != j and (box2[i] == box2[j] or box3[i] == box3[j])) tf = 0;
      }
      if(tf) ans[1] = i;
   }

   for(int i=1; i+k<=n; i+=k){
      int bi = box1[ans[i]], box;
      for(int j=1; j<=n; j++){
         if(j != ans[i] and bi == box1[j]){
            box = box2[j]; 
            break;
         }
      }

      for(int j : res2[box]){
         if(bi == box1[j]) continue;
         ans[i+k] = j;
      }
   }

   vvi c(n+1), r(n+1);
   while(c[1] == c[2]){
      for(int i=1; i<=n; i++) c[i].push_back((i-1) % b);
      sort(c.begin()+1, c.end());
   }
   int l = c[1].size();

   for(int i=1; i<=n; i++){
      vi tmp = c[i];
      sort(tmp.begin(), tmp.end());
      int x = tmp[0];
      if(x == tmp[l-1]) swap(c[i], c[x*k+1]);
   }

   for(int i=0; i<l; i++){
      vvi qry(b);
      for(int j=1; j<=n; j++) qry[c[j][i]].push_back(j);
      vvi res = shuffle(qry);

      for(int j=0; j<b; j++){
         int v;
         for(int x : res[j]){
            for(int u=1; u<=n; u+=k){
               if(x == ans[u]){
                  v = u;
                  break;
               }
            }
         }

         for(int x : res[j]) r[x].push_back(c[v][i]);
      }
   }

   for(int i=1; i<=n; i++){
      for(int j=1; j<=n; j++){
         if(c[i] == r[j]) ans[i] = j;
      }
   }

   ans.erase(ans.begin());
   return ans;
}

vector<int> solve(int N, int B, int K, int Q, int ST){
   n = N;
   b = B;
   k = K;

	if(k == 2) return solve1();
   else return solve2();
}

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