QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#726112 | #5423. Perfect Matching | ASnown | WA | 233ms | 14732kb | C++14 | 1.8kb | 2024-11-08 21:40:55 | 2024-11-08 21:40:55 |
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");
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)