# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
966511 |
2024-04-20T02:42:06 Z |
obokaman |
Game (IOI13_game) |
C++17 |
|
4647 ms |
134572 KB |
#include <iostream>
#include <vector>
#include <string>
#include "game.h"
using namespace std;
bool debug = false;//true;
bool safecheck = false;
typedef long long ll;
struct Node {
Node *l, *r;
int x;
ll val;
int prio;
ll gcd;
};
struct RowNode {
RowNode *l, *r;
int x;
Node* row;
Node* thick_row;
int prio;
};
Node* row(RowNode* t) {
return t ? t->row : nullptr;
}
Node* thick_row(RowNode* t) {
return t ? t->thick_row : nullptr;
}
ll gcd(Node* t) {
return t ? t->gcd : -1;
}
ll val(Node* t) {
return t ? t->val : -1;
}
ll gcdrec(ll a, ll b) {
return a == 0 ? b : gcdrec(b%a, a);
}
ll gcd(ll a, ll b) {
if (a == -1 || b == -1) return a == -1 ? b : a;
return gcdrec(a, b);
}
Node* init_node(int x, ll val) {
Node* t = new Node;
t->l = t->r = nullptr;
t->x = x;
t->val = t->gcd = val;
t->prio = rand();
return t;
}
void update(Node* t) {
if (t) {
t->gcd = gcd(gcd(gcd(t->l), t->val), gcd(t->r));
}
}
// x in l
void split(Node* t, Node*& l, Node*& r, int x) {
if (!t) {
l = r = nullptr;
} else {
if (x < t->x) {
r = t;
split(t->l, l, t->l, x);
} else {
l = t;
split(t->r, t->r, r, x);
}
update(t);
}
}
void merge(Node*& t, Node* l, Node* r) {
if (!l || !r) {
t = l ? l : r;
} else {
if (l->prio > r->prio) { /// arj ! Tenia <, en vez de >.
t = l;
merge(t->r, t->r, r);
} else {
t = r;
merge(t->l, l, t->l);
}
update(t);
}
}
void print(Node* t) {
if (t) {
cout << "[";
print(t->l);
cout << " " << t->x << "|" << t->val << "|" << t->gcd << "-" << t->prio << " ";
print(t->r);
cout << "]";
}
}
void print(RowNode* t, int indent = 0) {
if (t) {
indent+=2;
print(t->l, indent);
cout << endl;
string sp(indent, ' ');
cout << sp << "x=" << t->x << endl;
cout << sp << "row=";
print(t->row);
cout << endl << sp << "thickrow=";
print(t->thick_row);
cout << endl;
print(t->r, indent);
indent-=2;
}
}
void update_x(Node*& t, int x, ll val) {
Node* t1, *t2, *t3;
if (debug) {
cout << "Going to update " << x << " " << val << endl;
print(t);
cout << endl;
}
split(t, t1, t2, x-1);
split(t2, t2, t3, x);
if (debug) {
cout << "Updating:";
print(t2);
cout << endl;
}
if (!t2) t2 = init_node(x, val);
else t2->val = t2->gcd = val;
merge(t, t1, t2);
merge(t, t, t3);
if (debug) {
cout << "Aaaand.. updated!" << endl;
print(t);
cout << endl;
}
}
ll gcdRS(Node* t, int R, int S) {
Node* t1, *t2, *t3;
split(t, t1, t2, R-1);
split(t2, t2, t3, S);
ll res = gcd(t2);
merge(t, t1, t2);
merge(t, t, t3);
return res;
}
// gcd([x, \infy))
ll queryR(RowNode* t, int x, int R, int S) {
if (debug) {
cout << "QueryR: x=" << x << endl;
print(t);
cout << endl << endl;
}
if (!t) return -1;
else if (x < t->x) return gcd(gcdRS(thick_row(t->r), R, S),
gcd(gcdRS(row(t), R, S),
queryR(t->l, x, R, S)));
else if (x == t->x) {
ll a = gcdRS(thick_row(t->r), R, S);
ll b = gcdRS(row(t), R, S);
if (debug) {
cout << "answer = gcd(" << a << "," << b << ")" << endl;
}
return gcd(a, b);
}
else return queryR(t->r, x, R, S);
}
// gcd((-\infy, x])
ll queryL(RowNode* t, int x, int R, int S) {
if (debug) {
cout << "QueryL: x=" << x << endl;
print(t);
cout << endl << endl;
}
if (!t) return -1;
else if (x > t->x) return gcd(gcdRS(thick_row(t->l), R, S),
gcd(gcdRS(row(t), R, S),
queryL(t->r, x, R, S)));
else if (x == t->x) return gcd(gcdRS(thick_row(t->l), R, S),
gcdRS(row(t), R, S));
else return queryL(t->l, x, R, S);
}
// gcd of [P, Q]x[R, S]
ll query(RowNode* t, int P, int Q, int R, int S) {
if (debug) {
cout << "Query " << P << " " << Q << " " << R << " " << S << endl;
}
if (!t) return -1;
if (t->x < P) return query(t->r, P, Q, R, S);
else if (t->x > Q) return query(t->l, P, Q, R, S);
else {
if (debug) {
cout << P << "<=" << t->x << "<=" << Q << endl;
cout << "Going for QueryR and QueryL" << endl;
}
ll a = gcdRS(row(t), R, S);
ll b = queryR(t->l, P, R, S);
ll c = queryL(t->r, Q, R, S);
if (debug) {
cout << "myrow:" << a << " qR(t->l): "
<< b << " qL(t->r): " << c << endl;
}
return gcd(a, gcd(b, c));
}
}
ll find_gcd(Node* t, int Q) {
if (!t) return -1;
if (t->x == Q) return t->val;
else {
return find_gcd(Q < t->x ? t->l : t->r, Q);
}
}
void pointUpdateThickrow(RowNode*& t, int Q) {
// We don't need to fully recalculate thickrow, because only x=Q had
// changed.
Node* t1, *t2, *t3;
split(t->thick_row, t1, t2, Q-1);
split(t2, t2, t3, Q);
ll newval = gcd( find_gcd(thick_row(t->l), Q),
gcd( find_gcd(thick_row(t->r), Q), find_gcd(t->row, Q)) );
if (!t2) t2 = init_node(Q, newval);
else t2->val = t2->gcd = newval;
merge(t->thick_row, t1, t2);
merge(t->thick_row, t->thick_row, t3);
}
RowNode* find(RowNode* t, int P) {
if (!t) {
return nullptr;
}
else if (P < t->x) {
return find(t->l, P);
}
else if (P > t->x) {
return find(t->r, P);
}
else {
return t;
}
}
void copy(Node* src, Node*& dst) {
if (!src) dst = nullptr;
else {
dst = new Node;
copy(src->l, dst->l);
copy(src->r, dst->r);
dst->x = src->x;
dst->val = src->val;
dst->prio = src->prio;
dst->gcd = src->gcd;
}
}
Node* join(Node* t1, Node* t2) {
Node* t;
if (!t1 && !t2) t = nullptr;
else if (!t1) copy(t2, t);
else if (!t2) copy(t1, t);
else {
if (debug) {
cout << "Join t1=";
print(t1);
cout << endl;
cout << " with t2=";
print(t2);
cout << endl;
}
if (t1->prio < t2->prio) swap(t1, t2);
t = new Node;
Node* t2l, *t2x, *t2r;
ll t2gcd = gcd(t2);
split(t2, t2l, t2x, t1->x-1);
split(t2x, t2x, t2r, t1->x);
if (debug) {
cout << "Splitting t2l/t2x/t2r: ";
print(t2l);
cout << "/";
print(t2x);
cout << "/";
print(t2r);
cout << endl;
}
t->x = t1->x;
// Maybe I don't need t->val for thickrows?
t->val = gcd(val(t1), val(t2x));
t->gcd = gcd(gcd(t1), t2gcd);
t->prio = t1->prio;
t->l = join(t1->l, t2l);
t->r = join(t1->r, t2r);
if (debug) {
cout << "Before merging t2l/t2x/t2r: ";
print(t2l);
cout << "/";
print(t2x);
cout << "/";
print(t2r);
cout << endl;
}
merge(t2, t2l, t2x);
merge(t2, t2, t2r);
if (debug) {
cout << "Finished joining (maybe swapped) t1=";
print(t1);
cout << endl;
cout << " with t2=";
print(t2);
cout << endl;
}
}
return t;
}
// P in l.
void split(RowNode* t, RowNode*& l, RowNode*& r, int P) {
if (!t) {
l = r = nullptr;
} else {
if (P < t->x) {
r = t;
split(t->l, l, t->l, P);
} else {
l = t;
split(t->r, t->r, r, P);
}
t->thick_row = join(join(thick_row(t->l), t->row), thick_row(t->r));
}
}
void set_rec(RowNode*& t, int P, int Q, ll val, int prio) {
if (!t) {
if (debug) {
cout << "new RowNode" << endl;
}
t = new RowNode;
t->l = t->r = nullptr;
t->x = P;
t->row = init_node(Q, val);
t->prio = prio;
} else {
if (prio > t->prio) {
if (debug) {
cout << "insert RowNode" << endl;
}
// We know (from previous find(...)) that P is not available, we
// will insert it here.
RowNode* child = t;
t = new RowNode;
t->x = P;
split(child, t->l, t->r, P);
if (debug) {
cout << "After split:" << endl;
cout << "L:";
print(t->l);
cout << endl << "R:";
print(t->r);
cout << endl;
}
t->row = init_node(Q, val);
// (Q,val) will be updated as part of pointUpdateThickrow
if (debug) {
cout << "Before join:" << endl;
cout << endl << "Original thick_rows, L: ";
print(thick_row(t->l));
cout << endl << "Original thick_rows, R: ";
print(thick_row(t->r));
cout << endl;
}
t->thick_row = join(thick_row(t->l), thick_row(t->r));
if (debug) {
cout << "After join:" << endl;
cout << endl << "Original thick_rows, L: ";
print(thick_row(t->l));
cout << endl << "Original thick_rows, R: ";
print(thick_row(t->r));
cout << endl;
}
t->prio = prio;
} else {
if (debug) {
cout << "set_rec " << P << " " << Q << " " << val << endl;
print(t);
cout << endl;
}
if (P < t->x) set_rec(t->l, P, Q, val, prio);
else if (P == t->x) update_x(t->row, Q, val);
else set_rec(t->r, P, Q, val, prio);
}
}
pointUpdateThickrow(t, Q);
}
void set(RowNode*& t, int P, int Q, ll val) {
if (find(t, P)) {
if (debug) {
cout << "Found P=" << P << endl;
}
set_rec(t, P, Q, val, 0);
} else {
if (debug) {
cout << "Not found P=" << P << endl;
}
set_rec(t, P, Q, val, rand());
}
}
RowNode* globalt = nullptr;
vector<vector<ll> > W;
bool check_wh(Node* t, int ca, int cb, int ra, int rb) {
if (!safecheck || !t) return true;
ll val = -1;
for (int i=ra;i<=rb;++i) {
val = gcd(val, W[i][t->x]);
}
bool c1 = val == t->val;
if (!c1) {
cerr << "Failure checking val of "
<< ca << " " << cb << " " << ra << " " << rb << endl;
cerr << "Should be " << val << ", found " << t->val << endl;
print(t);
}
ll vgcd = -1;
for (int i=ra;i<=rb;++i) {
for (int j=ca;j<=cb;++j) {
vgcd = gcd(vgcd, W[i][j]);
}
}
bool c2 = vgcd == t->gcd;
if (!c2) {
cerr << "Failure checking gcd of "
<< ca << " " << cb << " " << ra << " " << rb << endl;
cerr << "Should be " << vgcd << ", found " << t->gcd << endl;
print(t);
}
bool cl = check_wh(t->l, ca, t->x-1, ra, rb);
bool cr = check_wh(t->r, t->x+1, cb, ra, rb);
return c1 && c2 && cl && cr;
}
bool check_wh(RowNode* t, int a, int b) {
if (!safecheck || !t) return true;
bool c1 = check_wh(t->row, 0, W[0].size()-1, t->x, t->x);
bool c2 = check_wh(t->thick_row, 0, W[a].size()-1, a, b);
if (!c1) {
cerr << "Failure checking t->row" << endl;
}
if (!c2) {
cerr << "Failure checking t->thick_row" << endl;
}
bool cl = check_wh(t->l, a, t->x-1);
bool cr = check_wh(t->r, t->x+1, b);
return c1 && c2 && cl && cr;
}
void init(int R, int C) {
if (safecheck) W.resize(R, vector<ll>(C));
}
void update(int P, int Q, ll K) {
if (debug) {
cout << "Before update:" << endl;
print(globalt);
for (int i = 0; i < (int)W.size(); ++i) {
for (int j = 0; j < (int)W[i].size(); ++j) {
cout << W[i][j] << " ";
}
cout << endl;
}
}
set(globalt, P, Q, K);
if (safecheck) {
W[P][Q] = K;
if (debug) {
cout << "After update: " << endl;
}
if (!check_wh(globalt, 0, W.size()-1)) {
cout << "Failed!" << endl;
if (debug) {
print(globalt);
for (int i = 0; i < (int)W.size(); ++i) {
for (int j = 0; j < (int)W[i].size(); ++j) {
cout << W[i][j] << " ";
}
cout << endl;
}
}
}
}
}
ll calculate(int P, int Q, int R, int S) {
ll slow = -1;
if (safecheck) {
for (int i=P;i<=R;++i) {
for (int j=Q;j<=S;++j) {
slow = gcd(slow, W[i][j]);
}
}
}
ll res = query(globalt, P, R, Q, S);
if (res == -1) res = 0;
if (safecheck) {
if (slow == -1) slow = 0;
if (slow != res) {
cout << "Error! " << P << " " << Q << " " << R << " " << S << endl;
cout << "Actual: " << slow << " Returned:" << res << endl;
print(globalt);
for (int i = 0; i < (int)W.size(); ++i) {
for (int j = 0; j < (int)W[i].size(); ++j) {
cout << W[i][j] << " ";
}
cout << endl;
}
// debug=true;
// query(globalt, P, R, Q, S);
// debug=false;
}
}
return res == -1 ? 0 : res;
}
//#include "game.h"
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
436 KB |
Output is correct |
6 |
Correct |
1 ms |
432 KB |
Output is correct |
7 |
Correct |
1 ms |
436 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
356 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
929 ms |
11496 KB |
Output is correct |
5 |
Correct |
341 ms |
11092 KB |
Output is correct |
6 |
Correct |
1280 ms |
8548 KB |
Output is correct |
7 |
Correct |
1582 ms |
8440 KB |
Output is correct |
8 |
Correct |
1027 ms |
7488 KB |
Output is correct |
9 |
Correct |
1507 ms |
9256 KB |
Output is correct |
10 |
Correct |
1352 ms |
7888 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
432 KB |
Output is correct |
4 |
Correct |
0 ms |
436 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
600 KB |
Output is correct |
12 |
Correct |
1000 ms |
16756 KB |
Output is correct |
13 |
Correct |
2206 ms |
10596 KB |
Output is correct |
14 |
Correct |
479 ms |
5732 KB |
Output is correct |
15 |
Correct |
3171 ms |
14456 KB |
Output is correct |
16 |
Correct |
1903 ms |
19000 KB |
Output is correct |
17 |
Correct |
1780 ms |
15272 KB |
Output is correct |
18 |
Correct |
3603 ms |
19180 KB |
Output is correct |
19 |
Correct |
2576 ms |
20324 KB |
Output is correct |
20 |
Correct |
3046 ms |
20092 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
432 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
764 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
899 ms |
11756 KB |
Output is correct |
13 |
Correct |
330 ms |
11148 KB |
Output is correct |
14 |
Correct |
1268 ms |
8532 KB |
Output is correct |
15 |
Correct |
1553 ms |
8272 KB |
Output is correct |
16 |
Correct |
1018 ms |
7508 KB |
Output is correct |
17 |
Correct |
1509 ms |
9028 KB |
Output is correct |
18 |
Correct |
1346 ms |
7988 KB |
Output is correct |
19 |
Correct |
980 ms |
16740 KB |
Output is correct |
20 |
Correct |
2181 ms |
10824 KB |
Output is correct |
21 |
Correct |
473 ms |
5740 KB |
Output is correct |
22 |
Correct |
3135 ms |
14280 KB |
Output is correct |
23 |
Correct |
1870 ms |
19020 KB |
Output is correct |
24 |
Correct |
1759 ms |
15388 KB |
Output is correct |
25 |
Correct |
3548 ms |
19620 KB |
Output is correct |
26 |
Correct |
2606 ms |
20572 KB |
Output is correct |
27 |
Correct |
3004 ms |
20076 KB |
Output is correct |
28 |
Correct |
816 ms |
36340 KB |
Output is correct |
29 |
Correct |
1395 ms |
62644 KB |
Output is correct |
30 |
Correct |
1930 ms |
27356 KB |
Output is correct |
31 |
Correct |
1390 ms |
22100 KB |
Output is correct |
32 |
Correct |
507 ms |
10236 KB |
Output is correct |
33 |
Correct |
694 ms |
10784 KB |
Output is correct |
34 |
Correct |
1658 ms |
48620 KB |
Output is correct |
35 |
Correct |
1726 ms |
32880 KB |
Output is correct |
36 |
Correct |
3316 ms |
60960 KB |
Output is correct |
37 |
Correct |
2587 ms |
54872 KB |
Output is correct |
38 |
Correct |
2829 ms |
54772 KB |
Output is correct |
39 |
Correct |
2261 ms |
40172 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
923 ms |
11508 KB |
Output is correct |
13 |
Correct |
330 ms |
11268 KB |
Output is correct |
14 |
Correct |
1273 ms |
8528 KB |
Output is correct |
15 |
Correct |
1534 ms |
8408 KB |
Output is correct |
16 |
Correct |
1022 ms |
7496 KB |
Output is correct |
17 |
Correct |
1503 ms |
9064 KB |
Output is correct |
18 |
Correct |
1354 ms |
8304 KB |
Output is correct |
19 |
Correct |
970 ms |
16916 KB |
Output is correct |
20 |
Correct |
2175 ms |
10832 KB |
Output is correct |
21 |
Correct |
464 ms |
5732 KB |
Output is correct |
22 |
Correct |
3142 ms |
14108 KB |
Output is correct |
23 |
Correct |
1886 ms |
19048 KB |
Output is correct |
24 |
Correct |
1757 ms |
15260 KB |
Output is correct |
25 |
Correct |
3514 ms |
19352 KB |
Output is correct |
26 |
Correct |
2604 ms |
20288 KB |
Output is correct |
27 |
Correct |
3020 ms |
19844 KB |
Output is correct |
28 |
Correct |
835 ms |
36140 KB |
Output is correct |
29 |
Correct |
1473 ms |
62860 KB |
Output is correct |
30 |
Correct |
1947 ms |
27512 KB |
Output is correct |
31 |
Correct |
1414 ms |
21976 KB |
Output is correct |
32 |
Correct |
516 ms |
10232 KB |
Output is correct |
33 |
Correct |
707 ms |
10652 KB |
Output is correct |
34 |
Correct |
1671 ms |
48724 KB |
Output is correct |
35 |
Correct |
1736 ms |
32856 KB |
Output is correct |
36 |
Correct |
3495 ms |
60912 KB |
Output is correct |
37 |
Correct |
2638 ms |
54948 KB |
Output is correct |
38 |
Correct |
2916 ms |
54840 KB |
Output is correct |
39 |
Correct |
1180 ms |
72964 KB |
Output is correct |
40 |
Correct |
2331 ms |
134572 KB |
Output is correct |
41 |
Correct |
2926 ms |
53564 KB |
Output is correct |
42 |
Correct |
3345 ms |
42480 KB |
Output is correct |
43 |
Correct |
2667 ms |
108192 KB |
Output is correct |
44 |
Correct |
728 ms |
10648 KB |
Output is correct |
45 |
Correct |
2420 ms |
39864 KB |
Output is correct |
46 |
Correct |
4571 ms |
130644 KB |
Output is correct |
47 |
Correct |
4609 ms |
108772 KB |
Output is correct |
48 |
Correct |
4647 ms |
126716 KB |
Output is correct |
49 |
Correct |
0 ms |
344 KB |
Output is correct |