QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#102498#5154. ETAw4p3r#WA 166ms44152kbC++201.7kb2023-05-03 14:00:512023-05-03 14:00:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-03 14:00:56]
  • 评测
  • 测评结果:WA
  • 用时:166ms
  • 内存:44152kb
  • [2023-05-03 14:00:51]
  • 提交

answer

#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e - 6
#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 pa pair<int, int>
#define fr first
#define sd second
#define pb push_back
#define db double
#define MEM(a) memset(a, 0, sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch = getchar();
	ll s = 0, w = 1;
	while (ch < '0' || ch > '9') {if (ch == '-')w = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
#define int ll
#define N 1000010
int d[N];
vector<int>v[N];
signed main()
{
	// freopen("E.out", "w", stdout);
	int a = read(), b = read();
	int ta = a, tb = b;
	if (a < b - 1) {cout << "impossible\n"; return 0;}
	else if (a == b - 1)
	{
		cout << b << " " << b - 1 << '\n';
		FOR(i, 2, b)cout << 1 << ' ' << i << '\n';
		return 0;
	}
	int t = int(1e6) / b;
	b *= t, a *= t;
	assert(b * (b - 1) / 2 >= a);
	swap(a, b);
	b -= a - 1;
	int l = 0, r = a, ans = 0;
	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (mid * (mid - 1) / 2 + (a - 1 - mid) * (mid - 1) >= b) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	for (int i = 2; i <= ans + 1; i++)d[i] = i - 2, b -= d[i];
	for (int i = ans + 2; i <= a; i++)
	{
		if (b >= ans - 1) {b -= ans - 1, d[i] = ans - 1;}
		else {d[i] = b; break;}
	}
	FOR(i, 2, a)d[i]++;
	FOR(i, 1, a)v[d[i]].pb(i);
	// FOR(i, 1, a)cout << d[i] << ' '; cout << endl;
	int s=0;
	FOR(i,1,a)s+=d[i];
	assert(s/__gcd(s,a)==ta&&a/__gcd(s,a)==tb);
	FOR(p, 1, ans)for (int x : v[p])cout << v[p - 1][0] << ' ' << x << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 26828kb

input:

1/2

output:

2 1
1 2

result:

ok 

Test #2:

score: 0
Accepted
time: 10ms
memory: 26772kb

input:

1/3

output:

impossible

result:

ok 

Test #3:

score: -100
Wrong Answer
time: 166ms
memory: 44152kb

input:

7/4

output:

1 2
1 750004
1 750005
1 750006
1 750007
1 750008
1 750009
1 750010
1 750011
1 750012
1 750013
1 750014
1 750015
1 750016
1 750017
1 750018
1 750019
1 750020
1 750021
1 750022
1 750023
1 750024
1 750025
1 750026
1 750027
1 750028
1 750029
1 750030
1 750031
1 750032
1 750033
1 750034
1 750035
1 750036...

result:

wrong answer Integer parameter [name=y] equals to 750004, violates the range [1, 1]