hiho week 146 register

Ended

Participants:548

Verdict:Accepted
Score:100 / 100
Submitted:2017-04-17 09:39:34

Lang:G++

Edit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXK = 1000005;
int N, M, K, solution[MAXK];
long long getSumLU(long long x, long long y) { // Get the sum of submatrix[1 .. x, 1 .. y]
    if (x > y) swap(x, y);
    return x * (x + 1) * ((x << 1) + 1) / 6 + ((y - x) * x * (x + 1) >> 1);
}
long long getSumRD(long long x, long long y) { // Get the sum of submatrix [x .. x + N - 1, y .. y + M - 1]. At least one of x and y should be 1
    if (1 == x) return getSumLU(N, y + M - 1) - getSumLU(N, y - 1);
    return getSumLU(x + N - 1, M) - getSumLU(x - 1, M);
}
struct Ans {
    int x, y;
    Ans(int x = MAXK, int y = MAXK): x(x), y(y) {}
}ans;
bool operator <(const Ans &A, const Ans &B) {
    return A.x + A.y < B.x + B.y || (A.x + A.y == B.x + B.y && A.x < B.x);
}
Ans solve(int x, int y) {
    int d = solution[(K - getSumRD(x, y) % K) % K];
    return d >= 0 ? Ans(x + d, y + d) : Ans();
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX