답안 #2910 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
2910	2013-08-03T09:40:57 Z	astein	게임 (IOI13_game)	C++	37 / 100	13000 ms	7664 KB

game

#include "game.h"
#include <cstring>
#include <queue>
#include <cstdio>
#include <cassert>

using namespace std;

struct Node {
  Node *lu, *ld, *ru, *rd;
  Node* parent;

  int sx, sy, ex, ey;
  long long value;

  Node(int x1, int y1, int x2, int y2, long long v) : sx(x1), sy(y1), ex(x2), ey(y2), value(v) { lu = 0, ld = 0, ru = 0, rd = 0; }
};

Node* root;

void init(int R, int C) {
	root = new Node(0, 0, R - 1, C - 1, 0);
}

long long gcd(long long a, long long b) {
  if (a == 0 && b == 0) return 0;
  if (a == 0) return b;
  if (b == 0) return a;
  long long c = a % b;
  while (c) {
    a = b, b = c, c = a % b;
  }
  return b;
}

void update(int x, int y, long long v) {
  Node* next = root;
  while (true) {
    int sx = next->sx, sy = next->sy, ex = next->ex, ey = next->ey;
    if (sx == ex && sy == ey && x == sx && y == sy) {
      //printf("%d, %d - %d, %d : %lld\n", sx, sy, ex, ey, v);
      next->value = v;
      break;
    }

    int mx = (sx + ex) / 2;
    int my = (sy + ey) / 2;

    if (sx <= x && x <= mx) {
      if (sy <= y && y <= my) {
        // lu
        if (!next->lu) { 
          Node* child = new Node(sx, sy, mx, my, 0);
          child->parent = next;
          next->lu = child;
        }
        next = next->lu;
      } else {
        // ru
        if (!next->ru) { 
          Node* child = new Node(sx, my + 1, mx, ey, 0);
          child->parent = next;
          next->ru = child;
        }
        next = next->ru;
      }
    } else {
      if (sy <= y && y <= my) {
        // ld
        if (!next->ld) { 
          Node* child = new Node(mx + 1, sy, ex, my, 0);
          child->parent = next;
          next->ld = child;
        }
        next = next->ld;
      } else {
        // rd
        if (!next->rd) {
          Node* child = new Node(mx + 1, my + 1, ex, ey, 0);
          child->parent = next;
          next->rd = child;
        }
        next = next->rd;
      }
    }
  }

  Node* up;
  while (next != root) {
    next = next->parent;

    long long g = 0;
    if (next->lu) g = gcd(next->lu->value, g);
    if (next->ru) g = gcd(next->ru->value, g);
    if (next->ld) g = gcd(next->ld->value, g);
    if (next->rd) g = gcd(next->rd->value, g);
    next->value = g;
    //printf("%d, %d - %d, %d : %lld\n", next->sx, next->sy, next->ex, next->ey, next->value);
  }
}

long long calculate(int x1, int y1, int x2, int y2) {
  queue<Node*> Q;
  Q.push(root);

  long long g = 0;
  while (!Q.empty()) {
    Node* now = Q.front(); Q.pop();
    if (x1 <= now->sx && y1 <= now->sy && now->ex <= x2 && now->ey <= y2) {
      g = gcd(now->value, g);
      continue;
    }
    if (now->sx > x2) continue;
    if (now->sy > y2) continue;
    if (now->ex < x1) continue;
    if (now->ey < y1) continue;

    if (now->lu) Q.push(now->lu);
    if (now->ld) Q.push(now->ld);
    if (now->ru) Q.push(now->ru);
    if (now->rd) Q.push(now->rd);
  }

  return g;
}

void clear(Node* now) {
  queue<Node*> Q;
  Q.push(now);
  int numNode = 0;
  while (!Q.empty()) {
    now = Q.front(); Q.pop();

		if (now->lu) Q.push(now->lu);
	  if (now->ld) Q.push(now->ld);
	  if (now->ru) Q.push(now->ru);
	  if (now->rd) Q.push(now->rd);
	  now->parent = 0;
	  numNode++;
	  delete now;
  }
}

Subtask #1
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	1240 KB	Output is correct
2	Correct	1240 KB	Output is correct
3	Correct	1240 KB	Output is correct
4	Correct	1240 KB	Output is correct
5	Correct	1240 KB	Output is correct
6	Correct	1240 KB	Output is correct
7	Correct	1240 KB	Output is correct
8	Correct	1240 KB	Output is correct
9	Correct	1240 KB	Output is correct
10	Correct	1240 KB	Output is correct
11	Correct	1240 KB	Output is correct
12	Correct	1240 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1240 KB	Output is correct
2	Correct	0 ms	1240 KB	Output is correct
3	Correct	0 ms	1240 KB	Output is correct
4	Correct	1580 ms	7420 KB	Output is correct
5	Correct	1120 ms	7412 KB	Output is correct
6	Correct	1012 ms	7664 KB	Output is correct
7	Correct	1140 ms	7312 KB	Output is correct
8	Correct	756 ms	4716 KB	Output is correct
9	Correct	1088 ms	7664 KB	Output is correct
10	Correct	1080 ms	7592 KB	Output is correct
11	Correct	0 ms	1240 KB	Output is correct

Subtask #3
0.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1240 KB	Output is correct
2	Correct	0 ms	1240 KB	Output is correct
3	Correct	0 ms	1240 KB	Output is correct
4	Correct	0 ms	1240 KB	Output is correct
5	Correct	0 ms	1240 KB	Output is correct
6	Correct	0 ms	1240 KB	Output is correct
7	Correct	0 ms	1240 KB	Output is correct
8	Correct	0 ms	1240 KB	Output is correct
9	Correct	0 ms	1240 KB	Output is correct
10	Correct	0 ms	1240 KB	Output is correct
11	Correct	0 ms	1240 KB	Output is correct
12	Correct	8376 ms	4536 KB	Output is correct
13	Execution timed out	13000 ms	2736 KB	Program timed out
14	Halted	0 ms	0 KB	-

Subtask #4
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1240 KB	Output is correct
2	Correct	0 ms	1240 KB	Output is correct
3	Correct	0 ms	1240 KB	Output is correct
4	Correct	0 ms	1240 KB	Output is correct
5	Correct	0 ms	1240 KB	Output is correct
6	Correct	0 ms	1240 KB	Output is correct
7	Correct	0 ms	1240 KB	Output is correct
8	Correct	0 ms	1240 KB	Output is correct
9	Correct	0 ms	1240 KB	Output is correct
10	Correct	0 ms	1240 KB	Output is correct
11	Correct	0 ms	1240 KB	Output is correct
12	Correct	1548 ms	7420 KB	Output is correct
13	Correct	1128 ms	7412 KB	Output is correct
14	Correct	988 ms	7664 KB	Output is correct
15	Correct	1132 ms	7312 KB	Output is correct
16	Correct	764 ms	4716 KB	Output is correct
17	Correct	1068 ms	7664 KB	Output is correct
18	Correct	1092 ms	7592 KB	Output is correct
19	Correct	8380 ms	4536 KB	Output is correct
20	Execution timed out	13000 ms	2736 KB	Program timed out
21	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1240 KB	Output is correct
2	Correct	0 ms	1240 KB	Output is correct
3	Correct	0 ms	1240 KB	Output is correct
4	Correct	0 ms	1240 KB	Output is correct
5	Correct	0 ms	1240 KB	Output is correct
6	Correct	0 ms	1240 KB	Output is correct
7	Correct	0 ms	1240 KB	Output is correct
8	Correct	0 ms	1240 KB	Output is correct
9	Correct	0 ms	1240 KB	Output is correct
10	Correct	0 ms	1240 KB	Output is correct
11	Correct	0 ms	1240 KB	Output is correct
12	Correct	1548 ms	7420 KB	Output is correct
13	Correct	1120 ms	7412 KB	Output is correct
14	Correct	972 ms	7664 KB	Output is correct
15	Correct	1112 ms	7312 KB	Output is correct
16	Correct	752 ms	4716 KB	Output is correct
17	Correct	1072 ms	7664 KB	Output is correct
18	Correct	1088 ms	7592 KB	Output is correct
19	Correct	8352 ms	4536 KB	Output is correct
20	Execution timed out	13000 ms	2736 KB	Program timed out
21	Halted	0 ms	0 KB	-

답안 #2910

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 0.0 / 26.0

Subtask #4 0.0 / 17.0

Subtask #5 0.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
0.0 / 26.0

Subtask #4
0.0 / 17.0

Subtask #5
0.0 / 20.0