QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#410467 | #3019. Probe Droids | Lspeed# | RE | 1ms | 3788kb | C++20 | 3.9kb | 2024-05-14 02:38:32 | 2024-05-14 02:38:33 |
Judging History
answer
#include<bits/stdc++.h>
#define x first
#define y second
#define eb emplace_back
#define pb push_back
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define sz(x) (int)(x).size()
#define make_unique(x) sort(all(x)), (x).erase(unique(all(x)), (x).end())
using namespace std;
typedef long long i64;
//typedef __int128 i128;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<i64> vl;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<i64,i64> pll;
typedef tuple<int,int,int> iii;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
int readInt() { int a; scanf("%d",&a); return a; }
i64 readLong() { i64 a; scanf("%lld",&a); return a; }
char readChar() { char a; scanf(" %c",&a); return a; }
double readDouble() { double a; scanf(" %lf",&a); return a; }
void readString(char *s) { scanf(" %s",s); }
const int mod = 998244353;
int add(int a, int b) { return ((a+=b)>=mod) ? a-mod:a; }
int mul(int a, int b) { return a*1ll*b%mod; }
int pw(int a, int b) {
int ans = 1, res = a;
for(int i = 1; i <= b; i*=2, res=mul(res,res)) {
if(i&b) {
ans = mul(ans, res);
}
}
return ans;
}
typedef long long ll;
#define rep(i,a,b) for(int i = a; i < (b); ++i)
struct Frac { ll p, q; };
template<class F>
Frac fracBS(F f, ll N) {
bool dir = 1, A = 1, B = 1;
Frac lo{0,1}, hi{1,1};
if(f(lo)) return lo;
assert(f(hi));
while(A || B) {
ll adv = 0, step = 1;
for(int si = 0; step; (step *= 2) >>= si) {
adv += step;
Frac mid{lo.p*adv + hi.p, lo.q*adv + hi.q};
if (abs(mid.p) > N || mid.q > N || dir == !f(mid)) {
adv -= step; si = 2;
}
}
hi.p += lo.p * adv;
hi.q += lo.q * adv;
dir = !dir;
swap(lo, hi);
A = B;
B = !!adv;
}
return dir ? hi:lo;
}
// ==== divsum
// divsum(to, c, k, m) = sum(from i = 0 to to-1) floor(k*i+c/m)
typedef unsigned long long ull;
ull sumsq(ull to) { return to/2*((to-1)|1); }
ull divsum(ull to, ull c, ull k, ull m) {
ull res = k / m * sumsq(to) + c / m * to;
k %= m; c %= m;
if(!k) return res;
ull to2 = (to*k+c)/m;
return res + (to-1) * to2 - divsum(to2, m-1-c, m, k);
}
ll gcd(ll a, ll b) {
if(b == 0) return a;
return gcd(b, a%b);
}
int main() {
// fracBS([](Frac f) { // return smth }, N);
int n, m, q;
scanf("%d %d %d",&n,&m,&q);
while(q--) {
i64 rank;
scanf(" %lld",&rank);
if(rank <= m-1) {
printf("1 %d\n",(int)rank+1);
continue;
}
if(rank > n*1ll*(m-1)) {
printf("%lld 1\n",rank-n*1ll*(m-1)+1);
continue;
}
// assume n>=2 and m>=2
int N = max(n,m);
Frac res = fracBS([&](Frac f) {
// f = p/q
// you automaticallly have m-1 points
ll ans = m-1;
if(f.p != 0) {
// y/x <= p/q
// y <= x*p/q
ll limit = ((n-1)*f.q+f.p-1)/f.p;
if(limit-1 >= m-1) {
// then no edge case
// divsum(to, c, k, m) = sum(from i = 0 to to-1) floor(k*i+c/m)
ans += divsum(m, 0, f.p, f.q);
} else {
ans += (m-1-limit+1)*1ll*(n-1);
ans += divsum(limit, 0, f.p, f.q);
}
}
if(ans >= rank) return true;
else return false;
}, N);
Frac f = res;
// you automaticallly have m-1 points
ll ans = m-1;
// y/x <= p/q
// y <= x*p/q
ll limit = ((n-1)*f.q+f.p-1)/f.p;
if(limit-1 >= m-1) {
// then no edge case
// divsum(to, c, k, m) = sum(from i = 0 to to-1) floor(k*i+c/m)
ans += divsum(m, 0, f.p, f.q);
} else {
ans += (m-1-limit+1)*1ll*(n-1);
ans += divsum(limit, 0, f.p, f.q);
}
ll g = gcd(f.p,f.q);
f.p /= g;
f.q /= g;
// find the maximum k such that
// k*f.p <= n-1
// k*f.q <= m-1
int k = min((n-1)/f.p, (m-1)/f.q);
i64 lo = ans-k, hi = ans;
assert(lo < rank && rank <= hi);
printf("%lld %lld\n",(rank-lo)*f.p+1,(rank-lo)*f.q+1);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3784kb
input:
3 5 3 1 14 8
output:
1 2 3 1 3 5
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3788kb
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...
output:
500004 500004 500010 500010 499954 499954 499972 499972 499965 499965 499990 499990 499971 499971 499985 499985 500047 500047 500021 500021 500042 500042 500023 500023 499999 499999 499977 499977 500041 500041 500026 500026 500002 500002 499998 499998 499969 499969 499968 499968 500033 500033 500029...
result:
ok 200 numbers
Test #3:
score: -100
Runtime Error
input:
1000000 1000000 100 791524265480 310246148308 965405638061 748161462511 437425441834 859125430870 318755212730 838283037379 290597520864 840800992509 318819733413 235852029334 308150887842 829080735481 847795824828 806338877319 658498289208 599749991035 951485631667 503061373811 165065406989 4217028...