QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#201436 | #5154. ETA | whsyhyyh# | WA | 1ms | 5720kb | C++14 | 1.1kb | 2023-10-05 14:21:25 | 2023-10-05 14:21:25 |
Judging History
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