QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#334598 | #5423. Perfect Matching | yllcm | WA | 294ms | 32248kb | C++14 | 1.6kb | 2024-02-22 08:35:43 | 2024-02-22 08:35:43 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
int x = 0; bool op = false;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 2e5 + 10;
int n;
int a[N], vis[N], vm[N];
vector<pii> G[N];
vector<pii> mat;
void dfs(int u, int fid) {
vector<int> V;
for(auto t : G[u]) {
int id = t.FR, v = t.SE;
if(vis[v])continue;
vis[v] = true; dfs(v, id);
if(vm[id] == false)V.pb(id);
}
if((V.size() & 1) && fid)V.pb(fid);
for(int i = 0; i < V.size(); i += 2)
vm[V[i]] = vm[V[i + 1]] = true, mat.pb({V[i], V[i + 1]});
return ;
}
void solve() {
n = read();
for(int i = 1; i <= n; i++)a[i] = read();
map<int, int> id; int tot = 0;
for(int i = 1; i <= n; i++) {
if(!id.count(i + a[i]))id[i + a[i]] = ++tot;
if(!id.count(i - a[i]))id[i - a[i]] = ++tot;
G[id[i + a[i]]].pb({i, id[i - a[i]]});
G[id[i - a[i]]].pb({i, id[i + a[i]]});
}
vector<pii>().swap(mat);
for(int i = 1; i <= tot; i++)if(!vis[i])vis[i] = true, dfs(i, 0);
if(mat.size() != n / 2)return puts("No"), void();
puts("Yes");
for(auto t : mat)printf("%d %d\n", t.FR, t.SE);
for(int i = 1; i <= tot; i++) {
vector<pii>().swap(G[i]);
vis[i] = false;
}
for(int i = 1; i <= n; i++)vm[i] = false;
return ;
}
int main() {
int test = read();
while(test--)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 8368kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
Yes 1 4 5 2 6 3 Yes 1 3 4 2 No
result:
ok 3 Cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 294ms
memory: 32248kb
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:
No No No No No No No No No No
result:
wrong answer std outputs a valid answer while participant doesn't (test case 1)