QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#726138 | #5423. Perfect Matching | ASnown | RE | 3ms | 8740kb | C++14 | 1.8kb | 2024-11-08 21:53:22 | 2024-11-08 21:53:22 |
Judging History
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);
}
詳細信息
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...