QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#726112#5423. Perfect MatchingASnownWA 233ms14732kbC++141.8kb2024-11-08 21:40:552024-11-08 21:40:55

Judging History

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

  • [2024-11-08 21:40:55]
  • 评测
  • 测评结果:WA
  • 用时:233ms
  • 内存:14732kb
  • [2024-11-08 21:40:55]
  • 提交

answer

#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popcount(x) (__builtin_popcount((x)))
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
using ll=long long;
using uint=uint32_t;
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
const int N = 2e5+25;
int n;
int a[N];
vector<int> VL,VR;
vector<pair<int,int>> e[N];
int dep[N];
vector<pair<int,int>> G;
int dfs(int u,int fa) {
   dep[u]=dep[fa]+1;
   vector<int> es;
   for(auto [v,id]:e[u]) if(!dep[v]) {
      auto p=dfs(v,u); 
      if(p) G.emplace_back(id,p);
      else es.emplace_back(id);
   }
   for(int i=0;i+1<es.size();i+=2)
      G.emplace_back(es[i],es[i+1]);
   return es.size()&1?es.back():0;
}
signed main() {
#ifndef ONLINE_JUDGE
#endif
   cin.tie(nullptr)->sync_with_stdio(false);
   int T; cin>>T; while(T--)
   Solve();
}
void Solve() {
   VL.clear(),VR.clear(),G.clear();
   for(int i=1;i<=n+n;i++) e[i].clear(),dep[i]=0;
   cin>>n;
   for(int i=1;i<=n;i++) {
      cin>>a[i];
      VL.emplace_back(i-a[i]);
      VR.emplace_back(i+a[i]);
   }
   sort(ALL(VL)),VL.erase(unique(ALL(VL)),VL.end());
   sort(ALL(VR)),VR.erase(unique(ALL(VR)),VR.end());
   for(int i=1;i<=n;i++) {
      int l=upper_bound(ALL(VL),i-a[i])-VL.begin();
      int r=upper_bound(ALL(VR),i+a[i])-VR.begin()+n;
      e[l].emplace_back(r,i);
      e[r].emplace_back(l,i);
   }
   for(int i=1;i<=n+n;i++) if(!dep[i]&&dfs(i,0)) 
      return void(puts("No"));
   puts("Yes");
   for(auto [u,v]:G) printf("%d %d\n",u,v);
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 10164kb

input:

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

output:

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

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 233ms
memory: 14732kb

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:

Yes
79 139
202 244
289 310
316 322
337 382
397 451
460 463
481 517
520 526
556 568
619 661
736 763
790 853
904 934
979 988
1090 1105
1162 1219
1273 1285
1294 1405
1411 1456
1459 1531
1555 1561
1588 1615
1618 1630
1651 1669
1684 1723
1738 1915
1972 2026
2029 2092
2155 2197
2290 2305
2350 2353
2419 24...

result:

wrong output format Expected integer, but "Yes" found (test case 1)