QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201436#5154. ETAwhsyhyyh#WA 1ms5720kbC++141.1kb2023-10-05 14:21:252023-10-05 14:21:25

Judging History

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

  • [2023-10-05 14:21:25]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5720kb
  • [2023-10-05 14:21:25]
  • 提交

answer

#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define N 1000010
#define LL long long
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define drep(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int rd() {
	int res=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
	return res*f;
}
int A,B,n,m,sum;
int U[N],V[N];
int main() {
	scanf("%d",&A);
	char ch=getchar();
	scanf("%d",&B);
	int g=__gcd(A,B);A/=g,B/=g;
	if(A+1<B) {
		printf("impossible");
		return 0;
	}
	int k=(int)ceil(2.0*A/(B*B)+1.0/B);
	n=B*k,sum=A*n/B;
	int now=2;
	while(now<=n) {
		if(now-1+n-now>sum) break;
		sum-=now-1,U[++m]=now,V[m]=now-1;
//		cerr<<"FUCK "<<now<<" "<<sum<<endl;
		now++;
	}
	while(now<=n-1) U[++m]=now,V[m]=1,now++,sum--;
	if(now<=n) U[++m]=now,V[m]=sum+1;
	printf("%d %d\n",n,m);
	rep(i,1,m) printf("%d %d\n",U[i],V[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5720kb

input:

1/2

output:

2 1
2 1

result:

ok 

Test #2:

score: 0
Accepted
time: 1ms
memory: 3772kb

input:

1/3

output:

impossible

result:

ok 

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 5596kb

input:

7/4

output:

8 7
2 1
3 2
4 3
5 4
6 1
7 1
8 3

result:

FAIL Wrong average distance, got 15/8, wanted 7/4