Submission #1280594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280594		aliali	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	0 / 100	2110 ms	271052 KiB

mushrooms

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define ar array
#define boost ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int N = 1e6 + 12, INF = 1e18 + 7, mod = 1e9 + 7;
signed main () {
  boost
  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    vector<int>v(n + 1), v2(n + 1);
    for(int i = 1; i <= n; ++i){
      cin >> v[i];
    }
    for(int i = 1; i <= n; ++i){
      cin >> v2[i];
    }
    vector<pair<int, int>>v3;
    for(int i = 1; i <= n; ++i){
      if(v[i] >= n + 1 and v2[i] <= n){
        v3.push_back({3, i});
        swap(v[i], v2[i]);
      }  
    }
    for(int x = 1; x <= n; ++x){
      int loc = -1, loc2 = -1;
      for(int i = 1; i <= n; ++i){
        if(v[i] == x){
          loc = i;
        }
        if(v2[i] == x){
          loc2 = i;
        }
        if(loc != -1 or loc2 != -1){
          break;
        }
      }
      if(loc != -1){
        while(loc != x){
          v3.push_back({1, loc - 1});
          swap(v[loc - 1], v[loc]);
          loc -= 1;
        }
      } else {
        
        if(loc2 >= x){
          while(loc2 != x){
            v3.push_back({2, loc2 - 1});
            swap(v2[loc2 - 1], v2[loc2]);
            loc2 -= 1;
          }
        } else {
          while(loc2 != x){
            v3.push_back({2, loc2});
            swap(v2[loc2], v2[loc2 + 1]);
            loc2 += 1;
          }
        }
        v3.push_back({3, x});
        swap(v[x], v2[x]);
      }
    }
    int ind = 1;
    for(int x = n + 1; x <= n * 2; ++x){
      int loc = -1;
      for(int i = 1; i <= n; ++i){
        if(v2[i] == x){
          loc = i;
          break;
        }
      }
      while(loc != ind){
        v3.push_back({2, loc - 1});
        swap(v2[loc - 1], v2[loc]);
        loc -= 1;
      }
      ind += 1;
    }
    cout << (int)v3.size() << '\n';
    for(auto [x, y] : v3){
      cout << x << ' ' << y << '\n';
    }
  }
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 23
• Subtask 5: 0 / 19
• Subtask 6: 0 / 21