QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#102498 | #5154. ETA | w4p3r# | WA | 166ms | 44152kb | C++20 | 1.7kb | 2023-05-03 14:00:51 | 2023-05-03 14:00:56 |
Judging History
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]