成功 -90 掉青

C WA on #2

D Idleness limit exceeded on pretest 2（我也不知道是个啥东西

C：

#include<iostream>
#include<cstdio>
#include<queue>
#include<bitset>
#define int long long
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rpe(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair <int,int>
#define mp make_pair
#define st first
#define nd second
using namespace std;

const int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};
const char dc[5]={'-','U','D','L','R'};
const int MAXN=1000+5;
int n,m;
char a[MAXN][MAXN];
bitset <MAXN> b[MAXN];
int c[MAXN][MAXN];

il void mask(int i,int j)
{
    b[i][j]=1;
    rep(k,1,4) ++c[i+dx[k]][j+dy[k]];
}

il void bfs()
{
    queue <pii> q;
    rep(i,1,n) a[i][1]=='L' && (q.emplace(i,1),mask(i,1),1),a[i][m]=='R' && (q.emplace(i,m),mask(i,m),1); // L,R
    rep(j,1,m) a[1][j]=='U' && (q.emplace(1,j),mask(1,j),1),a[n][j]=='D' && (q.emplace(n,j),mask(n,j),1); // U,D

    pii ck; int x,y,nx,ny;
    while(!q.empty())
    {
        ck=q.front(); q.pop();
        x=ck.st,y=ck.nd;

        rep(i,1,4)
        {
            nx=x+dx[i],ny=y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m || b[nx][ny] || a[nx][ny]!=dc[i]) continue;
            q.emplace(nx,ny),mask(nx,ny);
        }
    }
}

il void solve(int __Ti)
{
    cin>>n>>m;
    rep(i,1,n) rep(j,1,m) cin>>a[i][j];
    rep(i,0,n+1) rep(j,0,m+1) b[i][j]=0,c[i][j]=0;

    bfs();

    cerr<<"{b}\n";
    rep(i,1,n) {rep(j,1,m) cerr<<b[i][j]; cerr<<'\n';}

    cerr<<"{c}\n";
    rep(i,1,n) {rep(j,1,m) cerr<<c[i][j]; cerr<<'\n';}

    int ans=0;
    rep(i,1,n) rep(j,1,m) !b[i][j] && c[i][j]<4 && (++ans);
    cout<<ans<<'\n';
}

signed main()
{
    ios::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
    int __T; cin>>__T; rep(__Ti,1,__T) solve(__Ti);
    return 0;
}

D：

#include<iostream>
#include<cstdio>
#include<vector>
#define int long long
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rpe(i,a,b) for(int i=(a);i>=(b);--i)
#define pii pair <int,int>
#define mp make_pair
#define st first
#define nd second
#define pb emplace_back
using namespace std;

const int MAXN=2e5+5;
int n,a[MAXN],c0,c1,c2;
vector <pii> v;

il void check(int x,int y) {if(abs(a[x]-a[y])!=1) {cerr<<":)================= at "<<x<<' '<<y<<'\n'; int qwq=6; qwq/=0;}}

il void opt(int x,int y) {swap(a[x],a[y]),v.pb(x,y),check(x,y);}

il void solve(int __Ti)
{
    vector<pii>().swap(v);

    cin>>n;
    c0=c1=c2=0;
    rep(i,1,n) cin>>a[i],a[i]==0 ? ++c0 : a[i]==1 ? ++c1 : ++c2;

    { // 不需要操作
        bool qwq=1;
        rep(i,2,n) a[i]<a[i-1] && (qwq=0);
        if(qwq) return cout<<0<<'\n',void();
    }

    { // 判断是否所有 1 都在中间 ; 使应为 0/2 处存在至少一个 1
        bool qwq=1;
        rep(i,1,c0) a[i]==1 && (qwq=0);
        rep(i,n-c2+1,n) a[i]==1 && (qwq=0);

        if(qwq)
        {
            rep(i,1,c0) if(a[i]==2)
            {
                opt(i,c0+1);
                break;
            }
        }
    }

    //cerr<<"step 1:\n";
    //rep(i,1,n) cerr<<a[i]<<' '; cerr<<'\n';

    {
        int cnt=0;
        rep(i,1,c0) a[i]==1 && (++cnt);
        rep(i,n-c2+1,n) a[i]==1 && (++cnt);

        if(cnt>1)
        {
            int p=c0+1;
            rep(i,1,c0) if(a[i]==1)
            {
            	if(cnt==1) continue;
                while(p<n-c2+1 && a[p]!=0) ++p;
                opt(i,p),--cnt;
            }

            p=c0+1;
            rpe(i,n,n-c2+1) if(a[i]==1)
            {
            	if(cnt==1) continue;
                while(p<n-c2+1 && a[p]!=2) ++p;
                opt(i,p),--cnt;
            }
        }
    }

    //cerr<<"step 2:\n";
    //rep(i,1,n) cerr<<a[i]<<' '; cerr<<'\n';

    {
        int l=1,r=n;
        rep(i,1,c0) if(a[i]!=0) {l=i; break;}
        rpe(i,n,n-c2+1) if(a[i]!=2) {r=i; break;}

        int p=-1; bool op; // op: 0L 1R
        rep(i,1,c0) a[i]==1 && p==-1 && (p=i,op=0);
        rep(i,n-c2+1,n) a[i]==1 && p==-1 && (p=i,op=1);

        while(l<=c0 && r>=n-c2+1)
        {
            //cerr<<op<<' '<<l<<' '<<r<<' '<<p<<'\n';
            if(!op)
            {
                opt(p,r),p=r;
                while(a[r]==2 && r>=n-c2+1) --r;
                while(a[l]==0 && l<=c0) ++l;
            }
            else
            {
                opt(p,l),p=l;
                while(a[r]==2 && r>=n-c2+1) --r;
                while(a[l]==0 && l<=c0) ++l;
            }
            
            op=!op;
            
            //cerr<<">>> "; rep(i,1,n) cerr<<a[i]<<' '; cerr<<'\n';
        }
    }

    //cerr<<"step 3:\n";
    //rep(i,1,n) cerr<<a[i]<<' '; cerr<<'\n';
    
    rep(i,1,n-1) if(a[i]>a[i+1]) opt(i,i+1);
    
    cout<<v.size()<<'\n';
    for(auto i:v) cout<<i.st<<' '<<i.nd<<'\n';
}

signed main()
{
    ios::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
    int __T; cin>>__T; rep(__Ti,1,__T) solve(__Ti);
    return 0;
}