QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#334600#5423. Perfect MatchingyllcmWA 0ms8252kbC++141.6kb2024-02-22 08:38:462024-02-22 08:38:47

Judging History

你现在查看的是最新测评结果

  • [2024-02-22 08:38:47]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:8252kb
  • [2024-02-22 08:38:46]
  • 提交

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)