Submission #966511

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
966511	2024-04-20T02:42:06 Z	obokaman	Game (IOI13_game)	C++17	100 / 100	4647 ms	134572 KB

game

#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"

Subtask #1

10.0 / 10.0

#	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

Subtask #2

27.0 / 27.0

#	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

Subtask #3

26.0 / 26.0

#	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

Subtask #4

17.0 / 17.0

#	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

Subtask #5

20.0 / 20.0

#	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