QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#78151 | #5423. Perfect Matching | JinTianHao | AC ✓ | 494ms | 24020kb | C++17 | 2.4kb | 2023-02-17 09:30:16 | 2023-02-17 09:30:19 |
Judging History
answer
#include <bits/stdc++.h>
#define inf 1000000007
#define mod 1000000007
// #define int long long
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
template <typename T> void read(T &x){
x=0;char ch=getchar();int fh=1;
while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
x*=fh;
}
template <typename T> void write(T x) {
if (x<0) x=-x,putchar('-');
if (x>9) write(x/10);
putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
int n,a[100005],ed;
vector<int> numsl,numsr;
vector<pair<int,int>> g[200005];
int vis[200005],match[100005];
void dfs1(int x)
{
vis[x]=1;
ed+=g[x].size();
for(auto i:g[x])
if(!vis[i.first])
dfs1(i.first);
}
void dfs2(int x,int fa)
{
vis[x]=2;
vector<int> vec;
int tofa;
for(auto i:g[x])
if(i.first==fa) tofa=i.second;
else if(vis[i.first]!=2) dfs2(i.first,x);
for(auto i:g[x])
if(i.first!=fa&&!match[i.second])
vec.push_back(i.second);
if(vec.size()&1) vec.push_back(tofa);
for(int i=0;i<vec.size();i+=2)
match[vec[i]]=vec[i+1],match[vec[i+1]]=vec[i];
}
signed main()
{
// freopen("accepts.in","r",stdin);
// freopen("accepts.out","w",stdout);
int tc;read(tc);
while(tc--)
{
read(n);
numsl.clear();
numsr.clear();
for(int i=1;i<=n;++i)
{
read(a[i]);match[i]=0;
numsl.push_back(i-a[i]);
numsr.push_back(i+a[i]);
}
sort(numsl.begin(),numsl.end());
numsl.erase(unique(numsl.begin(),numsl.end()),numsl.end());
sort(numsr.begin(),numsr.end());
numsr.erase(unique(numsr.begin(),numsr.end()),numsr.end());
for(int i=1;i<=numsl.size()+numsr.size();++i)
g[i].clear(),vis[i]=0;
for(int i=1;i<=n;++i)
{
int x=upper_bound(numsl.begin(),numsl.end(),i-a[i])-numsl.begin();
int y=upper_bound(numsr.begin(),numsr.end(),i+a[i])-numsr.begin()+numsl.size();
g[x].push_back({y,i});
g[y].push_back({x,i});
}
bool flag=1;
for(int i=1;i<=numsl.size()+numsr.size();++i)
if(!vis[i])
{
ed=0;dfs1(i);ed/=2;
if(ed&1)
{
flag=0;break;
}
dfs2(i,0);
}
if(!flag) puts("No");
else
{
puts("Yes");
for(int i=1;i<=n;++i) vis[i]=0;
for(int i=1;i<=n;++i)
if(!vis[i]) write(i),putchar(' '),writeln(match[i]),vis[i]=vis[match[i]]=1;
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 8200kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 2 5 3 6 Yes 1 3 2 4 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: 0
Accepted
time: 259ms
memory: 18324kb
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 1 100000 2 33 3 79 4 6 5 7 8 9 10 13 11 12 14 15 16 20 17 18 19 26 21 22 23 25 24 99915 27 28 29 31 30 99 32 34 35 59 36 37 38 99908 39 40 41 42 43 45 44 46 47 56 48 49 50 99920 51 52 53 248 54 55 57 58 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 80 75 76 77 78 81 82 83 84 85 89 86 88 87 97 90 ...
result:
ok 10 Cases (10 test cases)
Test #3:
score: 0
Accepted
time: 4ms
memory: 8088kb
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 9 28 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 34 30 31 32 33 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 68 60 61 62 63 64 65 66 67 69 74 70 71 72 73 75 100 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 Yes ...
result:
ok 10 Cases (10 test cases)
Test #4:
score: 0
Accepted
time: 223ms
memory: 24020kb
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: 494ms
memory: 18460kb
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 1 4547 2 1932 3 24074 4 9 5 1492 6 140 7 1055 8 97 10 91206 11 449 12 2782 13 14 15 4917 16 7994 17 3227 18 1033 19 405 20 241 21 22355 22 24734 23 24 25 72 26 1088 27 99313 28 89504 29 33 30 97820 31 1158 32 44 34 163 35 82 36 730 37 11617 38 383 39 20594 40 105 41 54113 42 85 43 45 46 1832 47 ...
result:
ok 10 Cases (10 test cases)
Test #6:
score: 0
Accepted
time: 151ms
memory: 8224kb
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 1 4 2 10 3 5 6 9 7 20 8 997 11 30 12 16 13 991 14 15 17 18 19 44 21 25 22 23 24 55 26 28 27 31 29 38 32 35 33 34 36 37 39 40 41 43 42 51 45 49 46 50 47 48 52 60 53 54 56 61 57 59 58 69 62 64 63 80 65 81 66 67 68 70 71 83 72 73 74 75 76 88 77 78 79 82 84 95 85 91 86 90 87 118 89...
result:
ok 1000 Cases (1000 test cases)