题目详情提交记录（0）

题解（作者的第一个双超越100%）

userId_undefined
复仇者_sxwwsด้้（加团队
时间刺客空间掌握者时空双修者出道萌新荣耀黄金分治·分治练习生

2024-12-07 20:31:45

发布于：河北

203阅读
0回复
0点赞

样例6步，我15步

#include <cstdio>
using namespace std;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
	return x * f;
}
const int N = 60, M = 410, K = 820010;
int n, m, a[N][M], len[N], ans, q[K], b[N][M];
inline void Move(int x, int y){ a[x][++len[x]] = a[y][len[y]]; b[x][len[x]] = b[y][len[y]]; --len[y]; q[++ans] = y * 65 + x; }//单次移动 y -> x
inline void movenum(int x, int y, int z){ while(z--) Move(x, y); }//多次移动 y -> x
inline void movecol(int x, int y, int z){// 利用 y 填充 x 为 z 
	int num = 0; for(int i = 1; i <= m; ++i) num += (b[x][i] == z);
	if(num == m) return; if(num > m / 2){
		movenum(n + 1, y, m - num);
		for(int i = m; i; --i){ if(b[x][i] == z) Move(n + 1, x); else Move(y, x); }
		movenum(x, n + 1, num); movenum(x, y, m - num); movenum(y, n + 1, m - num);
	}else{
		movenum(n + 1, y, num);
		for(int i = m; i; --i){ if(b[x][i] == z) Move(y, x); else Move(n + 1, x); }
		movenum(x, y, num); movenum(x, n + 1, m - num); movenum(y, n + 1, num);
	}
	num = 0; for(int i = 1; i <= m; ++i) num += (b[y][i] == z); movenum(n + 1, x, num); 
	for(int i = m; i; --i){ if(b[y][i] == z) Move(x, y); else Move(n + 1, y); } movenum(y, n + 1, m);
}
inline void Qsort(int l, int r){//分治 
	if(l == r) return; int mid = l + r >> 1, x = l, y = r;
	for(int i = l; i <= r; ++i) for(int j = 1; j <= m; ++j) b[i][j] = (a[i][j] > mid);
	while(x <= mid && y > mid){
		int num = 0;
		for(int i = 1; i <= m; ++i) num += b[x][i] + b[y][i];
		if(num > m) movecol(y--, x, 1); else movecol(x++, y, 0);
	}
	Qsort(l, mid); Qsort(mid + 1, r);
}
inline void print(){ printf("%d\n", ans); for(int i = 1; i <= ans; ++i) printf("%d %d\n", q[i] / 65, q[i] % 65); }
int main(){
	n = read(); m = read();
	for(int i = 1; i <= n; ++i){
		len[i] = m;
		for(int j = 1; j <= m; ++j){
			a[i][j] = read();
		}
	}
	Qsort(1, n); print(); return 0;
}

看到这里，点亿个免费的赞吧

userId_undefined
去预览
0/2000

全部评论 5

  • userId_undefined
    老登转世

    hi~

    2024-12-07 来自 四川

    2
  • userId_undefined
    黑妞
    模拟·模拟练习生空间掌握者字符串·魔法使枚举·枚举小能手递归·套娃学徒贪心·贪心尝试者

    这人。。。

    2026-01-21 来自 江苏

    1
  • userId_undefined
    139****0839
    时间刺客空间掌握者秩序白银

    666666666666666666666

    2025-04-09 来自 广东

    1
  • userId_undefined
    青莲又失利了

    666666

    2025-04-05 来自 山东

    1
  • userId_undefined
    Jason
    空间掌握者倔强青铜多键裁决者快排信徒→排序之神造物者维度操控者
    #include <cstdio>
using namespace std;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
	return x * f;
}
const int N = 60, M = 410, K = 820010;
int n, m, a[N][M], len[N], ans, q[K], b[N][M];
inline void Move(int x, int y){ a[x][++len[x]] = a[y][len[y]]; b[x][len[x]] = b[y][len[y]]; --len[y]; q[++ans] = y * 65 + x; }//单次移动 y -> x
inline void movenum(int x, int y, int z){ while(z--) Move(x, y); }//多次移动 y -> x
inline void movecol(int x, int y, int z){// 利用 y 填充 x 为 z 
	int num = 0; for(int i = 1; i <= m; ++i) num += (b[x][i] == z);
	if(num == m) return; if(num > m / 2){
		movenum(n + 1, y, m - num);
		for(int i = m; i; --i){ if(b[x][i] == z) Move(n + 1, x); else Move(y, x); }
		movenum(x, n + 1, num); movenum(x, y, m - num); movenum(y, n + 1, m - num);
	}else{
		movenum(n + 1, y, num);
		for(int i = m; i; --i){ if(b[x][i] == z) Move(y, x); else Move(n + 1, x); }
		movenum(x, y, num); movenum(x, n + 1, m - num); movenum(y, n + 1, num);
	}
	num = 0; for(int i = 1; i <= m; ++i) num += (b[y][i] == z); movenum(n + 1, x, num); 
	for(int i = m; i; --i){ if(b[y][i] == z) Move(x, y); else Move(n + 1, y); } movenum(y, n + 1, m);
}
inline void Qsort(int l, int r){//分治 
	if(l == r) return; int mid = l + r >> 1, x = l, y = r;
	for(int i = l; i <= r; ++i) for(int j = 1; j <= m; ++j) b[i][j] = (a[i][j] > mid);
	while(x <= mid && y > mid){
		int num = 0;
		for(int i = 1; i <= m; ++i) num += b[x][i] + b[y][i];
		if(num > m) movecol(y--, x, 1); else movecol(x++, y, 0);
	}
	Qsort(l, mid); Qsort(mid + 1, r);
}
inline void print(){ printf("%d\n", ans); for(int i = 1; i <= ans; ++i) printf("%d %d\n", q[i] / 65, q[i] % 65); }
int main(){
	n = read(); m = read();
	for(int i = 1; i <= n; ++i){
		len[i] = m;
		for(int j = 1; j <= m; ++j){
			a[i][j] = read();
		}
	}
	Qsort(1, n); print(); return 0;
}

    昨天 来自 浙江

    0
    • userId_undefined
      Jason
      回复
      Jason
      #include <cstdio>
using namespace std;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
	return x * f;
}
const int N = 60, M = 410, K = 820010;
int n, m, a[N][M], len[N], ans, q[K], b[N][M];
inline void Move(int x, int y){ a[x][++len[x]] = a[y][len[y]]; b[x][len[x]] = b[y][len[y]]; --len[y]; q[++ans] = y * 65 + x; }//单次移动 y -> x
inline void movenum(int x, int y, int z){ while(z--) Move(x, y); }//多次移动 y -> x
inline void movecol(int x, int y, int z){// 利用 y 填充 x 为 z 
	int num = 0; for(int i = 1; i <= m; ++i) num += (b[x][i] == z);
	if(num == m) return; if(num > m / 2){
		movenum(n + 1, y, m - num);
		for(int i = m; i; --i){ if(b[x][i] == z) Move(n + 1, x); else Move(y, x); }
		movenum(x, n + 1, num); movenum(x, y, m - num); movenum(y, n + 1, m - num);
	}else{
		movenum(n + 1, y, num);
		for(int i = m; i; --i){ if(b[x][i] == z) Move(y, x); else Move(n + 1, x); }
		movenum(x, y, num); movenum(x, n + 1, m - num); movenum(y, n + 1, num);
	}
	num = 0; for(int i = 1; i <= m; ++i) num += (b[y][i] == z); movenum(n + 1, x, num); 
	for(int i = m; i; --i){ if(b[y][i] == z) Move(x, y); else Move(n + 1, y); } movenum(y, n + 1, m);
}
inline void Qsort(int l, int r){//分治 
	if(l == r) return; int mid = l + r >> 1, x = l, y = r;
	for(int i = l; i <= r; ++i) for(int j = 1; j <= m; ++j) b[i][j] = (a[i][j] > mid);
	while(x <= mid && y > mid){
		int num = 0;
		for(int i = 1; i <= m; ++i) num += b[x][i] + b[y][i];
		if(num > m) movecol(y--, x, 1); else movecol(x++, y, 0);
	}
	Qsort(l, mid); Qsort(mid + 1, r);
}
inline void print(){ printf("%d\n", ans); for(int i = 1; i <= ans; ++i) printf("%d %d\n", q[i] / 65, q[i] % 65); }
int main(){
	n = read(); m = read();
	for(int i = 1; i <= n; ++i){
		len[i] = m;
		for(int j = 1; j <= m; ++j){
			a[i][j] = read();
		}
	}
	Qsort(1, n); print(); return 0;
}

      昨天 来自 浙江

      0
    • userId_undefined
      Jason
      回复
      Jason
      #include <cstdio>
using namespace std;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
	return x * f;
}
const int N = 60, M = 410, K = 820010;
int n, m, a[N][M], len[N], ans, q[K], b[N][M];
inline void Move(int x, int y){ a[x][++len[x]] = a[y][len[y]]; b[x][len[x]] = b[y][len[y]]; --len[y]; q[++ans] = y * 65 + x; }//单次移动 y -> x
inline void movenum(int x, int y, int z){ while(z--) Move(x, y); }//多次移动 y -> x
inline void movecol(int x, int y, int z){// 利用 y 填充 x 为 z 
	int num = 0; for(int i = 1; i <= m; ++i) num += (b[x][i] == z);
	if(num == m) return; if(num > m / 2){
		movenum(n + 1, y, m - num);
		for(int i = m; i; --i){ if(b[x][i] == z) Move(n + 1, x); else Move(y, x); }
		movenum(x, n + 1, num); movenum(x, y, m - num); movenum(y, n + 1, m - num);
	}else{
		movenum(n + 1, y, num);
		for(int i = m; i; --i){ if(b[x][i] == z) Move(y, x); else Move(n + 1, x); }
		movenum(x, y, num); movenum(x, n + 1, m - num); movenum(y, n + 1, num);
	}
	num = 0; for(int i = 1; i <= m; ++i) num += (b[y][i] == z); movenum(n + 1, x, num); 
	for(int i = m; i; --i){ if(b[y][i] == z) Move(x, y); else Move(n + 1, y); } movenum(y, n + 1, m);
}
inline void Qsort(int l, int r){//分治 
	if(l == r) return; int mid = l + r >> 1, x = l, y = r;
	for(int i = l; i <= r; ++i) for(int j = 1; j <= m; ++j) b[i][j] = (a[i][j] > mid);
	while(x <= mid && y > mid){
		int num = 0;
		for(int i = 1; i <= m; ++i) num += b[x][i] + b[y][i];
		if(num > m) movecol(y--, x, 1); else movecol(x++, y, 0);
	}
	Qsort(l, mid); Qsort(mid + 1, r);
}
inline void print(){ printf("%d\n", ans); for(int i = 1; i <= ans; ++i) printf("%d %d\n", q[i] / 65, q[i] % 65); }
int main(){
	n = read(); m = read();
	for(int i = 1; i <= n; ++i){
		len[i] = m;
		for(int j = 1; j <= m; ++j){
			a[i][j] = read();
		}
	}
	Qsort(1, n); print(); return 0;
}

      昨天 来自 浙江

      0
    • userId_undefined
      Jason
      回复
      Jason
      #include <cstdio>
using namespace std;
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
	return x * f;
}
const int N = 60, M = 410, K = 820010;
int n, m, a[N][M], len[N], ans, q[K], b[N][M];
inline void Move(int x, int y){ a[x][++len[x]] = a[y][len[y]]; b[x][len[x]] = b[y][len[y]]; --len[y]; q[++ans] = y * 65 + x; }//单次移动 y -> x
inline void movenum(int x, int y, int z){ while(z--) Move(x, y); }//多次移动 y -> x
inline void movecol(int x, int y, int z){// 利用 y 填充 x 为 z 
	int num = 0; for(int i = 1; i <= m; ++i) num += (b[x][i] == z);
	if(num == m) return; if(num > m / 2){
		movenum(n + 1, y, m - num);
		for(int i = m; i; --i){ if(b[x][i] == z) Move(n + 1, x); else Move(y, x); }
		movenum(x, n + 1, num); movenum(x, y, m - num); movenum(y, n + 1, m - num);
	}else{
		movenum(n + 1, y, num);
		for(int i = m; i; --i){ if(b[x][i] == z) Move(y, x); else Move(n + 1, x); }
		movenum(x, y, num); movenum(x, n + 1, m - num); movenum(y, n + 1, num);
	}
	num = 0; for(int i = 1; i <= m; ++i) num += (b[y][i] == z); movenum(n + 1, x, num); 
	for(int i = m; i; --i){ if(b[y][i] == z) Move(x, y); else Move(n + 1, y); } movenum(y, n + 1, m);
}
inline void Qsort(int l, int r){//分治 
	if(l == r) return; int mid = l + r >> 1, x = l, y = r;
	for(int i = l; i <= r; ++i) for(int j = 1; j <= m; ++j) b[i][j] = (a[i][j] > mid);
	while(x <= mid && y > mid){
		int num = 0;
		for(int i = 1; i <= m; ++i) num += b[x][i] + b[y][i];
		if(num > m) movecol(y--, x, 1); else movecol(x++, y, 0);
	}
	Qsort(l, mid); Qsort(mid + 1, r);
}
inline void print(){ printf("%d\n", ans); for(int i = 1; i <= ans; ++i) printf("%d %d\n", q[i] / 65, q[i] % 65); }
int main(){
	n = read(); m = read();
	for(int i = 1; i <= n; ++i){
		len[i] = m;
		for(int j = 1; j <= m; ++j){
			a[i][j] = read();
		}
	}
	Qsort(1, n); print(); return 0;
}

      昨天 来自 浙江

      0
暂无数据

提交答案之后，这里将显示提交结果～

首页