Submission #966511

#	Time	Username	Problem	Language	Result	Execution time	Memory
966511		obokaman	Game (IOI13_game)	C++17	100 / 100	4647 ms	134572 KiB

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20