QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#83626#5528. Least Annoying Constructive ProblemCrysflyWA 2ms3368kbC++171.4kb2023-03-02 19:24:252023-03-02 19:24:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-02 19:24:26]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3368kb
  • [2023-03-02 19:24:25]
  • 提交

answer

// what is matter? never mind. 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 400005
#define inf 0x3f3f3f3f

int n,m,a[505][505];
pii e[maxn];

void sol0()
{
	For(i,1,n-1){
		a[i][n]=a[n][i]=(i-1)*(n/2)+1;
		int l=i,r=i;
		For(j,2,n/2){
			--l,++r;
			if(l==0)l=n-1;
			if(r==n)r=1;
			a[l][r]=a[r][l]=(i-1)*(n/2)+j;
		}
	}
	m=n*(n-1)/2;
	For(i,1,n)For(j,i+1,n)e[a[i][j]]=mkp(i,j);
}

void sol1()
{
	int i=1;
	For(_,1,n){
		int l=i,r=i+1;
		if(r==n+1)r=1;
		For(__,1,n/2){
			e[++m]=mkp(l,r);
			--l,++r;
			if(l==0)l=n;
			if(r==n+1)r=1;
		}
		i=l;
	}
}

int fa[9999];
int gf(int x){
	while(x^fa[x])x=fa[x]=fa[fa[x]];
	return x;
}
void chk(int l,int r){
	For(i,1,n)fa[i]=i;
	For(i,l,r){
		if(gf(e[i].fi)==gf(e[i].se))assert(0);
		fa[gf(e[i].fi)]=gf(e[i].se);
	}
}

signed main()
{
	n=read();
	if(n%2==0)sol0();
	else sol1();
	For(i,1,m) cout<<e[i].fi<<" "<<e[i].se<<"\n"; 
	For(i,1,m-(n-1)+1) chk(i,i+(n-1)-1);
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3368kb

input:

3

output:

1 2
3 1
2 3

result:

wrong answer Integer 1 violates the range [4, 3]