QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#772126 | #5423. Perfect Matching | juruoA | AC ✓ | 1203ms | 25604kb | C++14 | 4.1kb | 2024-11-22 17:09:04 | 2024-11-22 17:09:05 |
Judging History
answer
#include <bits/stdc++.h>
using std::bitset;
using std::cout;
using std::deque;
using std::endl;
using std::greater;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multimap;
using std::multiset;
using std::nth_element;
using std::pair;
using std::priority_queue;
using std::queue;
using std::reverse;
using std::set;
using std::sort;
using std::sqrt;
using std::stable_sort;
using std::string;
using std::swap;
using std::unique;
using std::upper_bound;
using std::vector;
typedef long long li;
typedef long double lf;
inline li read(){
li ans = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
f = (ch == '-') ? -1 : 1;
ch = getchar();
}
while(ch <= '9' && ch >= '0'){
ans = ans * 10 + (ch ^ 48);
ch = getchar();
}
return ans * f;
}
li p[2], n, a[200010];
struct edge{
li to, next, id;
} e[400010];
vector<pair<li, li>> ans;
li lenedge = 1, head[200010], vis[200010];
void addedge(li u, li v, li id){
// cout << u << " " << v << endl;
e[++lenedge] = {v, head[u], id};
head[u] = lenedge;
}
map<li, li> mp[2];
li getid(li x, li op){
if(!mp[op][x]) mp[op][x] = ++p[op];
return mp[op][x];
}
li visp[200010], fl;
li cnt;
li istree[200010];
void dfs1(li u){
visp[u] = 1;
for(li i = head[u]; i; i = e[i].next){
cnt++;
li v = e[i].to;
// cout << "find " << u << " " << v << endl;
if(!visp[v]){
dfs1(v);
istree[i >> 1] = 1;
// cout << "tree is " << u << " " << v << " " << e[i].id << endl;
}
}
}
void dfs2(li u, li fa){
vector<li> x;
for(li i = head[u]; i; i = e[i].next){
if((i ^ 1) == fa) continue;
if(vis[e[i].id]) continue;
if(istree[i >> 1]){
dfs2(e[i].to, i);
}
}
for(li i = head[u]; i; i = e[i].next){
if((i ^ 1) == fa) continue;
// cout << "vis " << e[i].id << " " << vis[e[i].id] << endl;
if(vis[e[i].id]) continue;
// cout << u << " " << e[i].to << endl;
// if((i ^ 1) == fa) continue;
x.push_back(e[i].id);
// cout << "in " << e[i].id << endl;
}
while(x.size() > 1){
li a = x.back(); x.pop_back();
li b = x.back(); x.pop_back();
// cout << "link1 " << a << " " << b << endl;
ans.push_back({a, b});
vis[a] = vis[b] = 1;
}
if(x.size()){
li a = x.back(); x.pop_back();
li b = e[fa ^ 1].id;
vis[a] = vis[b] = 1;
// cout << "link2 " << a << " " << b << endl;
ans.push_back({a, b});
}
}
int main(){
// freopen("wonderful.ans", "r", stdin);
// freopen("www.ww", "w", stdout);
li T = read();
while(T--){
fl = 1;
ans.clear();
n = read();
mp[0].clear(), mp[1].clear();
for(li i = 1; i <= n; i++) a[i] = read();
memset(head, 0, sizeof head);
memset(vis, 0, sizeof vis);
memset(visp, 0, sizeof visp);
memset(istree, 0, sizeof istree);
p[0] = p[1] = 0;
lenedge = 1;
for(li i = 1; i <= n; i++){
getid(a[i] - i, 0), getid(a[i] + i, 1);
}
for(li i = 1; i <= n; i++){
li idx = getid(a[i] - i, 0), idy = getid(a[i] + i, 1) + p[0];
addedge(idx, idy, i), addedge(idy, idx, i);
}
// cout << p[0] << " " << p[1] << endl;
for(li i = 1; i <= p[0] + p[1] && fl; i++){
if(visp[i]) continue;
// cout << "i = " << i << endl;
// cout << "vis 5 = " << vis[5] << endl;
dfs1(i);
// cout << "sb" << endl;
cnt /= 2;
// cout << "cnt = " << cnt << endl;
if(cnt % 2 == 1) fl = 0;
cnt = 0;
if(fl){
dfs2(i, 0);
}
}
if(!fl){
printf("No\n");
} else{
printf("Yes\n");
for(auto v : ans) printf("%lld %lld\n", v.first, v.second);
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 13988kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 4 1 2 5 3 6 Yes 3 1 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 456ms
memory: 23272kb
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 99977 99979 99821 99823 99980 99981 99929 99930 99994 99993 99940 99939 99928 99927 99894 99893 99891 99892 99873 99872 99985 99983 99937 99935 99925 99923 99814 99812 99795 99796 99771 99772 99727 99725 99723 99724 99706 99704 99699 99700 99673 99671 99640 99638 99627 99628 99586 99584 99549 99...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 5ms
memory: 13588kb
input:
10 100 28761184 28761185 28761186 28761187 28761188 28761189 28761190 28761191 -20675012 -20675013 -20675014 -20675015 -20675016 -20675017 -20675018 -20675019 -20675020 -20675021 -20675022 -20675023 -20675024 -20675025 -20675026 -20675027 -20675028 -20675029 -20675030 -20675031 -36758138 -36758139 -...
output:
Yes 1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 9 30 31 32 33 34 29 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 60 61 62 63 64 65 66 67 68 59 70 71 72 73 74 69 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 75 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 480ms
memory: 22500kb
input:
10 100000 -40608960 -40608959 -40608958 -40608957 -40608956 -40608955 -40608954 -40608953 -40608952 -40608951 -40608950 -40608949 -40608948 -40608947 -40608946 -40608945 -40608944 -40608943 -40608942 -40608941 -40608940 -40608939 -40608938 -40608937 -40608936 -40608935 -40608934 -40608933 -40608932 ...
output:
Yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok 10 Cases (10 test cases)
Test #5:
score: 0
Accepted
time: 1203ms
memory: 25604kb
input:
10 100000 0 -1 -2 3 2 5 6 7 -2 1 0 9 12 11 -8 13 8 -7 16 17 -10 19 22 21 22 23 4 -15 -18 -17 -6 -31 -14 25 32 -25 26 27 -32 31 38 -31 -32 -19 -30 -35 46 45 -48 -37 48 41 46 -43 -44 53 56 55 50 -27 52 61 62 -33 -18 19 64 45 46 -57 -8 -25 -26 -11 -22 49 -66 -65 -66 29 78 -15 74 83 12 83 14 85 86 -7 -5...
output:
Yes 89930 51424 90797 40204 84293 82260 81601 68474 63426 23563 81768 79940 89209 65068 78623 77535 71925 42616 50015 45416 63727 61582 94113 64578 71688 55765 87755 74925 86349 67712 97794 89613 98375 83954 85705 76781 96630 92136 62221 59568 77914 65037 64568 98085 91652 77633 75990 91261 93510 75...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 496ms
memory: 13908kb
input:
1000 1000 -2 0 3 4 6 7 4 7 6 9 11 9 10 12 16 13 16 17 18 20 19 19 24 22 25 23 28 25 26 27 30 32 31 34 36 37 34 37 37 40 42 43 44 45 43 44 46 45 50 48 51 49 54 55 52 55 54 57 56 61 60 61 64 65 64 67 65 66 67 68 71 73 73 75 76 77 78 75 76 78 82 79 80 81 83 83 87 88 90 89 90 93 92 93 95 94 96 96 100 97...
output:
No No No No No No Yes 987 986 963 962 952 951 913 912 858 857 771 770 740 739 728 727 721 720 719 718 705 704 700 699 664 663 600 599 584 583 503 502 456 455 444 443 418 417 407 406 405 404 343 342 319 318 310 309 263 262 261 260 211 210 193 192 180 179 156 155 148 147 128 127 108 107 73 72 48 47 34...
result:
ok 1000 Cases (1000 test cases)