QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410465#3019. Probe DroidsLspeed#RE 1ms3868kbC++203.8kb2024-05-14 02:33:102024-05-14 02:33:10

Judging History

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

  • [2024-05-14 02:33:10]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3868kb
  • [2024-05-14 02:33:10]
  • 提交

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);
}

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);
		}

		// 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: 1ms
memory: 3868kb

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: 3864kb

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...

output:


result: