QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#334600 | #5423. Perfect Matching | yllcm | WA | 0ms | 8252kb | C++14 | 1.6kb | 2024-02-22 08:38:46 | 2024-02-22 08:38:47 |
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]) {V.pb(id); 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 + 1 < 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);
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;
if(mat.size() != n / 2)return puts("No"), void();
puts("Yes");
for(auto t : mat)printf("%d %d\n", t.FR, t.SE);
return ;
}
int main() {
int test = read();
while(test--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 8252kb
input:
3 6 14 22 33 11 25 36 4 100 10 98 12 4 1 3 5 7
output:
No No No
result:
wrong answer std outputs a valid answer while participant doesn't (test case 1)