Submission #1238387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238387		Joon_Yorigami	The Collection Game (BOI21_swaps)	C++17	100 / 100	3 ms	452 KiB

swaps

#include <bits/stdc++.h>
#include "swaps.h"
using namespace std;
using ll=long long;
using vll=vector<long long>;
const ll inf=LONG_LONG_MAX;

void solve(int n,int v)
{
  vector<int> ans;
  for(int i=1;i<=n;i++)
    ans.push_back(i);
  vector<vll> swaps;
  for(int p=1;p<n;p<<=1)
  {
    for(int k=p;k>=1;k>>=1)
    {
      vector<vll>().swap(swaps);
      for(int j=k%p;j<=n-1-k;j+=k+k)
      {
        for(int i=0;i<=min(k-1,n-j-k-1);i++)
        {
          if((i+j)/(p*2)==(i+j+k)/(p*2))
          {
            schedule(ans[i+j],ans[i+j+k]);
            swaps.push_back(vll({i+j,i+j+k}));
          }
        }
      }
      vector<int> res = visit();
      for(int i=0;i<res.size();i++)
      {
        if(res[i]==0)
          swap(ans[swaps[i][0]],ans[swaps[i][1]]);
      }
    }
  }
  answer(ans);
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3-1: 3 / 3
• Subtask 3-2: 2 / 2
• Subtask 4-1: 9 / 9
• Subtask 4-2: 6 / 6
• Subtask 5-1: 9 / 9
• Subtask 5-2: 6 / 6
• Subtask 6-1: 21 / 21
• Subtask 6-2: 14 / 14
• Subtask 7-1: 9 / 9
• Subtask 7-2: 6 / 6