QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726138#5423. Perfect MatchingASnownRE 3ms8740kbC++141.8kb2024-11-08 21:53:222024-11-08 21:53:22

Judging History

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

  • [2024-11-08 21:53:22]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:8740kb
  • [2024-11-08 21:53:22]
  • 提交

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");
   assert(G.size()==n/2);
   for(auto [u,v]:G) printf("%d %d\n",u,v);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 8740kb

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
Runtime Error

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: