oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

factortiles Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

factortiles.html

With your help, Po has found the secret message hidden in the mantous (and eaten his fill). The clue led him to a deserted temple in the middle of the forest. In one of the rooms, Po found another note in the same flowery handwriting as the one on the grid of mantous. "Jump on the tiles and watch them move. Flatten them all to show the way." Keeping the note in his pocket and looking ahead, Po saw that there was a grid of raised tiles with mysterious inscriptions in the centre of the room. Oh no! Not another grid.

Tentatively, Po hopped onto one of them. Suddenly, the tile he was standing on, along with five others, began to move downwards, grinding to a halt as they reached ground level. Looking down at his feet, Po realized that the tile he was stepping on was inscribed with the number 20. Straining his eyes, he saw that the mysterious inscriptions were really numbers, and the five other tiles were numbered 1, 2, 4, 5 and 10. Realizing that these are the factors of the number 20, Po jumped to the number 10. The tiles numbered 1, 2, 5 and 10 shifted back to their raised position. Every time he jumped on a tile, all the tiles whose numbers are factors of that tile were toggled. Po sighed. Another math question! He could jump as high and far as he wanted with superb precision, but he wouldn't know where to jump.

Help Po out by figuring out what the grid of tiles will look like after he has jumped on a series of tiles. The tiles are numbered in a diagonal zigzag fashion. For example, for a grid size of 3, the tiles are numbered as such:

  1  2  6
  3  5  7
  4  8  9

And for a grid size of 4:

  1  2  6  7
  3  5  8 13
  4  9 12 14
 10 11 15 16

Given the grid size and the list of jumps Po makes, figure out what the end position of the tiles are. All tiles begin in a raised position.

Input

The first line contains two integers, n and m. 1 ≤ n, m ≤ 200. n represents the grid size and m represents the number of jumps Po will make.
The following m lines contain two integers each, r and c. Each pair of two integers, 0 ≤ r, c < 200 mean that Po will jump on grid tile (c, r).

For 20% of the test cases, 1 ≤ n, m ≤ 50.
For 50% of the test cases, 1 ≤ n, m ≤ 100.
For 100% of the test cases, 1 ≤ n, m ≤ 200.

Output

Output n lines representing the final state of the grid after Po has jumped on all the given tile positions. Each line should contain n characters exactly.
'1' represents a raised position and '0' represents a tile at ground position.

Sample Input

5 2
4 2
3 0

Sample Output

11111
11111
01111
11111
11011

Explanation

A square grid of size 5 is numbered like this.

  1  2  6  7 15
  3  5  8 14 16
  4  9 13 17 22
 10 12 18 21 23
 11 19 20 24 25

Po jumped on grid tile 20, causing tiles 1, 2, 4, 5, 10 and 20 to fall to ground position. Next, he jumped on grid tile 10, causing tile 1, 2, 5 and 10 to rise back up again. As a result, only grid tiles 4 and 20 are at ground position.

Tags

NOI 2011 Sec Selection Test 2, Number Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100101s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o factortiles -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.