|
这几天在练习CF的时候，有一题TLE了，这里是原题(CF 1600J):
J. Robot Factory
time limit per test: 1 second
memory limit per test: 256 megabytes
inputstandard input
outputstandard output
You have received data from a Bubble bot. You know your task is to make factory facilities, but before you even start, you need to know how big the factory is and how many rooms it has. When you look at the data you see that you have the dimensions of the construction, which is in rectangle shape: N x M.
Then in the next N lines you have M numbers. These numbers represent factory tiles and they can go from 0 to 15. Each of these numbers should be looked in its binary form. Because from each number you know on which side the tile has walls. For example number 10 in its binary form is 1010, which means that it has a wall from the North side, it doesn’t have a wall from the East, it has a wall on the South side and it doesn’t have a wall on the West side. So it goes North, East, South, West.
It is guaranteed that the construction always has walls on its edges. The input will be correct.
Your task is to print the size of the rooms from biggest to smallest.
Input
The first line has two numbers which are N and M, the size of the construction. Both are integers:
n
（
1
≤
n
≤
1
0
3
）
n（1≤n≤10^3）
n（1≤n≤103）
m
（
1
≤
m
≤
1
0
3
）
m（1≤m≤10^3）
m（1≤m≤103）
Next N x M numbers represent each tile of construction.
Output
Once you finish processing the data your output consists of one line sorted from biggest to smallest room sizes.
Example
input
4 5
9 14 11 12 13
5 15 11 6 7
5 9 14 9 14
3 2 14 3 14
output
9 4 4 2 1
一开始我就想到了用类BFS（就是BFS算法，但不是求距离）的方法进行写程。后来上传后，Test1和Test2均过关，但是在Test3时TLE了。我看了数据(因为是练习而非比赛)，发现n和m都是1000的数据量。我一开始以为是算法的问题，但是经过我的测算，好像是没有问题的。
最后，我设计了一个n平方运算量的n=1000, m=1000数据。发现关键问题在于输出的时候，太慢了。因为是10的6次方的数据，而我的设计是每个“地板块”都是一个房间，故此共有10的6次方的输出。运行了好一会儿，输出都没有输出完毕。
现在仔细想来，我是用的cin和cout，而非scanf和printf。或许用stdio.h库中的输入输出或许可以不用TLE。
从这里可以看出来：运行是正常“瞬间”完成的。而关键的时间消耗就是输出所消耗的。
于是乎，我尝试加上了
ios::sync_with_stdio(false);
结果再次上传，就发现AC了。我自己测试同样的数据，1秒钟就输出完毕了。由此可见，对于大数据的输入输出，要么用scanf和printf，要么就加上ios::sync_with_stdio(false);
最后附上我的两次submit：
TLE代码(131760367)
AC代码(132135194)
原题地址：CodeForces1600J Robot Factory
|