QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#59871#3019. Probe DroidsYaoBIG#TL 2ms3684kbC++172.6kb2022-11-01 22:00:342022-11-01 22:00:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-01 22:00:35]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3684kb
  • [2022-11-01 22:00:34]
  • 提交

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

output:


result: