50 lines
1.2 KiB
C++
50 lines
1.2 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
const int N = 200010;
|
||
int n, p;
|
||
queue<int> q[N]; // 模p的余数组成的队列数组
|
||
set<int> s; // 集合?
|
||
|
||
int main() {
|
||
int T;
|
||
cin >> T;
|
||
while (T--) {
|
||
cin >> n >> p;
|
||
// 如果p太大，就不用算了,因为即使 n+ n-1 也无法构建出一个p,这个可以根据测试用例去想一个特判
|
||
if (p >= 2 * n) {
|
||
for (int i = 1; i <= n; i++)
|
||
cout << i << " ";
|
||
cout << endl;
|
||
continue;
|
||
}
|
||
|
||
for (int i = 1; i <= n; i++) // 按 模p分组
|
||
q[i % p].push(i);
|
||
|
||
for (int i = 0; i < p; i++)
|
||
if (q[i].size())
|
||
s.insert(i); // 队列非空才加入, s里装的是 模p的余数
|
||
|
||
int x = 0;
|
||
while (q[x].empty())
|
||
x++;
|
||
|
||
int y = q[x].front();
|
||
q[x].pop();
|
||
cout << y << " ";
|
||
|
||
for (int i = 1; i <= n; i++) { // 还有n-1个数字需要输出
|
||
int f = (p - x % p) % p; // 防止x%p=0的特殊情况
|
||
if (q[f].empty())
|
||
s.erase(f), f = *s.begin(); // 没了就删除，f换成任意一个非空队列
|
||
x = q[f].front();
|
||
q[f].pop();
|
||
cout << x << " ";
|
||
if (q[f].empty())
|
||
s.erase(f);
|
||
}
|
||
cout << endl;
|
||
}
|
||
|
||
return 0;
|
||
} |