QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#707015 | #5423. Perfect Matching | StrangeSolver | TL | 1ms | 5580kb | C++14 | 2.1kb | 2024-11-03 14:20:58 | 2024-11-03 14:20:58 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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...