QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#725672#5423. Perfect Matchingbugmaker3243ML 2ms7916kbC++233.0kb2024-11-08 19:16:432024-11-08 19:16:43

Judging History

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

  • [2024-11-08 19:16:43]
  • 评测
  • 测评结果:ML
  • 用时:2ms
  • 内存:7916kb
  • [2024-11-08 19:16:43]
  • 提交

answer

#include<bits/stdc++.h>
#define N 500005
//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
#define gc() getchar()
#define fi first
#define se second
#define Kamisato return
#define Ayaka 0;
#define file(_s) freopen(#_s".in","r",stdin);freopen(#_s".out","w",stdout);
//#define CHECK_MEMORY ___JQH___
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf=1e9;
const ll INF=2e18;
bool Memory_Begin;
namespace IO{const int SIZE=(1<<21)+1;char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];int f,qr;inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf,fflush(stdout);}inline void putc(char x){*oS++=x;if(oS==oT)flush();}template <class I>inline void read(I &x){for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;}template <class I>inline void print(I x){if(!x)putc('0');if(x<0)putc('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)putc(qu[qr --]);}inline void reads(string &s){s.clear();for(c=gc();c<33||c>126;)c=gc();for(;c>=33&&c<=126;c=gc())s.push_back(c);}inline void prints(string s){for(char c:s)putc(c);}struct Flusher_ {~Flusher_(){flush();}}io_flusher_;}
using IO::read;using IO::putc;using IO::print;using IO::reads;using IO::prints;
template<class I>I updiv(I x,I y){return (x%y==0?x/y:x/y+1);}
template<class I>bool cmin(I &x,I y){if(x>y)return x=y,1;return 0;}
template<class I>bool cmax(I &x,I y){if(x<y)return x=y,1;return 0;}

int n,a[N],L,R;
map<int,int>mpL,mpR;
vector<pii>s[N];
bool vst[N];
int calc(int x)
{
	queue<int>q;
	q.push(x),vst[x]=1;
	int res=0;
	while(q.size())
	{
		int x=q.front();
		q.pop();
		res+=s[x].size();
		for(pii i:s[x])
		{
			int y=i.fi;
			if(!vst[y]) q.push(y),vst[y]=1;
		}
	}
	return res/2;
}
vector<pii>ans;
bool usefa[N];
void dfs(int x,int prt,int pre)
{
	vector<int>las;
	for(pii i:s[x])
	{
		int y=i.fi,id=i.se;
		if(y==prt) continue;
		dfs(y,x,id);
		if(!usefa[y]) las.push_back(id);
	}
	if(las.size()&1) las.push_back(pre),usefa[x]=1;
	if(n>10) return ;
	for(int i=0;i+1<(int)las.size();i+=2) ans.push_back({las[i],las[i+1]});
}
void solve()
{
	read(n);
	for(int i=1;i<=n;i++) read(a[i]),mpL[i-a[i]]=mpR[i+a[i]]=0;
	for(auto &p:mpL) p.se=++L;
	for(auto &p:mpR) p.se=L+(++R);
	for(int i=1;i<=n;i++)
	{
		int x=mpL[i-a[i]],y=mpR[i+a[i]];
		s[x].push_back({y,i});
		s[y].push_back({x,i});
	}
	for(int i=1;i<=L+R;i++)
		if(!vst[i])
		{
			if(calc(i)&1) return prints("No\n");
			dfs(i,0,0);
		}
	prints("Yes\n");
	for(pii p:ans) print(p.fi),putc(' '),print(p.se),putc('\n');
}
void clear()
{
	ans.clear(),mpL.clear(),mpR.clear();
	for(int i=1;i<=L+R;i++) s[i].clear(),vst[i]=usefa[i]=0;
	L=R=0;
}
bool Memory_End;
signed main()
{
#ifdef CHECK_MEMORY
	cerr<<"Memory: "<<(&Memory_End-&Memory_Begin)/1048576.0<<" MiB\n";
#endif
	int T; read(T);
	while(T--) solve(),clear();
	Kamisato Ayaka
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 7916kb

input:

3
6
14 22 33 11 25 36
4
100 10 98 12
4
1 3 5 7

output:

Yes
3 6
2 5
4 1
Yes
3 1
2 4
No

result:

ok 3 Cases (3 test cases)

Test #2:

score: -100
Memory Limit Exceeded

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:


result: