QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#707015#5423. Perfect MatchingStrangeSolverTL 1ms5580kbC++142.1kb2024-11-03 14:20:582024-11-03 14:20:58

Judging History

你现在查看的是最新测评结果

  • [2024-11-03 14:20:58]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:5580kb
  • [2024-11-03 14:20:58]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'
#define test() puts("**********");
#define hh() putchar('\n');
#define kg() putchar(' ');
using namespace std;
inline int read(){
    char ch=getchar();
    int v=1,u=0;
    while(!isdigit(ch)){
        if(ch=='-') v=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        u=(u<<1)+(u<<3)+ch-'0';
        ch=getchar();
    }
    return v*u;
}
void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
}
const int N=1e5+1,M=5000*5000+10;
int n,a[N],T,tot;
pair<int,int> lis[M];
unordered_set<int> s,dt;
bitset<M> vis;
signed main(){
    T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;i++) cin>>a[i];
        dt.clear();
        tot=0;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(j-i==abs(a[i]-a[j])){
                   tot++;
                   lis[tot]=make_pair(i,j);
                   dt.insert(i);
                   dt.insert(j);
                }
            }
        }
        bool ff=0;
        for(int i=1;i<=tot;i++){
            s.clear();
            for(int j=i;j<=tot;j++){
                if(s.count(lis[j].first)){
                	vis[j]=0;
					continue;
				} 
                if(s.count(lis[j].second)) {
                	vis[j]=0;
					continue;
				}
                vis[j]=1;
                s.insert(lis[j].first);
                s.insert(lis[j].second);
                if(s.size()==dt.size()){
                    ff=1;
                    puts("Yes");
                    for(int k=i;k<=j;k++){
                        if(vis[k]){
                            write(lis[k].first);
                            kg();
                            write(lis[k].second);
                            hh();
                        }
                    }
                    break;
                }
            }
            if(ff) break;
        }
        if(!ff){
            puts("No");
        }
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5580kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

Yes
1 4
2 5
3 6
Yes
1 3
2 4
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Time Limit Exceeded

input:

10
100000
0 -1 -2 -3 -4 -5 -2 -7 -8 -9 -10 -9 -12 13 14 15 -16 -17 -18 19 20 19 -22 -21 -20 -25 -26 -27 -28 -27 -26 31 30 29 -34 -35 -34 39 38 37 42 41 42 47 44 45 46 49 48 -53 -52 -51 -56 -55 -54 55 56 57 -58 -59 -60 61 62 63 64 65 64 67 66 69 70 73 72 73 74 73 76 75 74 79 80 81 -84 -83 -84 89 86 8...

output:


result: