QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#59871 | #3019. Probe Droids | YaoBIG# | TL | 2ms | 3684kb | C++17 | 2.6kb | 2022-11-01 22:00:34 | 2022-11-01 22:00:35 |
Judging History
answer
#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
using namespace std;
template<class A> string to_string(const A &v) {
bool first = 1;
string res = "{";
for (const auto &x: v) {
if (!first) res += ", ";
first = 0;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(const H &h, const T&... t) {
cerr << " " << to_string(h);
debug_out(t...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T>
T Euclidean(ll a, ll b, ll c, ll n) {
T res = 0;
if (a >= c || b >= c) {
res += T{a / c} * n * (n + 1) / 2;
res += T{b / c} * (n + 1);
a %= c;
b %= c;
}
if (a != 0) {
ll m = ((__int128)a * n + b) / c;
res += T{m} * n - Euclidean<T>(c, c - b - 1, a, m - 1);
}
return res;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m, q; cin >> n >> m >> q;
while (q--) {
ll need; cin >> need;
auto get = [&](int a, int c) {
if (c == 0) return 1ll * n * m - 1;
int lo = 0, hi = m;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (1ll * mid * a / c >= n - 1) hi = mid;
else lo = mid + 1;
}
ll ans = m - 1;
ans += 1ll * (m - hi) * (n - 1);
if (hi > 0) ans += Euclidean<ll>(a, 0, c, hi - 1);
return ans;
};
if (need > 1ll * (m - 1) * n) {
need -= 1ll * (m - 1) * n;
printf("%lld %d\n", need + 1, 1);
} else if (need <= m - 1) {
printf("%d %lld\n", 1, need + 1);
} else {
int al = 0, cl = 1, ar = 1, cr = 0;
while (1) {
int amid = al + ar;
int cmid = cl + cr;
if (amid >= n || cmid >= m) break;
if (get(amid, cmid) >= need) {
tie(ar, cr) = tie(amid, cmid);
} else {
tie(al, cl) = tie(amid, cmid);
}
}
auto [a, c] = tie(ar, cr);
ll sum = get(a, c);
// debug(need, sum, a, c);
int ansx = -1, ansy = -1;
revrep(x, 1, m - 1) {
if (1ll * x * a % c == 0) {
ll y = 1ll * x * a / c;
if (y > n - 1) continue;
if (sum == need) {
tie(ansx, ansy) = tie(x, y);
break;
} else sum--;
}
}
assert(ansx != -1);
printf("%d %d\n", ansy + 1, ansx + 1);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3684kb
input:
3 5 3 1 14 8
output:
1 2 3 1 3 5
result:
ok 6 numbers
Test #2:
score: -100
Time Limit Exceeded
input:
1000000 1000000 100 500000000003 500000000009 499999999953 499999999971 499999999964 499999999989 499999999970 499999999984 500000000046 500000000020 500000000041 500000000022 499999999998 499999999976 500000000040 500000000025 500000000001 499999999997 499999999968 499999999967 500000000032 5000000...