Origami

There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n (1 ≤ n ≤ 10⁶), indicating the length of the paper.
The second line contains n integers a₁, a₂, ..., a_n, which is a permutation of n, indicating the integers marked in the grids of the resulting sheet of paper from top to bottom.
It's guaranteed that the sum of n in all test cases will not exceed 10⁶.

C++14(g++5.4) 解法, 执行用时: 273ms, 内存消耗: 16268K, 提交时间: 2018-12-03 19:36:20

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int n,a[MAXN],p[MAXN],top,S[MAXN],g[MAXN];
bool ok(int x){
    for(int i=1;i<=n;i++) g[i]=0;
    for(int i=x;i+1<=n;i+=2){
        int l=p[i],r=p[i+1]; if(l>r)swap(l,r);
        g[l]=r; g[r]=-r;
    }
    top=0;
     for(int i=1;i<=n;i++) {
        if(g[i]>0)S[++top]=g[i];
        else if(g[i]<0){
            if(S[top]!=-g[i])return false;
            top--;
        }
    }
    return true;
}
 
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
         for(int i=1;i<=n;i++) scanf("%d",&a[i]),p[a[i]]=i;
        if(ok(2)&&ok(1)) puts("Yes");
        else puts("No");
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 277ms, 内存消耗: 9700K, 提交时间: 2020-03-15 21:43:56

#include<iostream>
using namespace std;
const int maxn=1e6+50;
int s[maxn],a,g[maxn],zb[maxn];
int top,n;
bool solve(int x)
{
	top=0;
	for(int i=0;i<=n;++i) g[i]=0;
	for(int i=x;i<n;i+=2)
	{
		int l=zb[i],r=zb[i+1];
		if(l>r) swap(l,r);
		g[l]=r;
		g[r]=-r;
	}
	for(int i=1;i<=n;++i)
	{
		if(g[i]>0) s[++top]=g[i];
		else if(g[i]<0)
		{
			if(s[top]!=-g[i]) return false;
			top--;
		}
	}
	return true;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;++i) scanf("%d",&a),zb[a]=i;
		if(solve(1)&&solve(2)) cout<<"Yes\n";
		else cout<<"No\n";
	}
}

详情