My solution
As the constraint is m*n<=10^6, this solution should work under 1 second but it's taking about 1871 ms in one of the TLE'd test case. Why could this be happening?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
void solve() {
int n, m; cin >> n >> m;
vector<pair<int, int> > v; v.reserve(n * m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
v[m * (i - 1) + j - 1] = {i, j};
}
}
bool low = true;
int l = 0, r = m * n - 1;
while (r >= l) {
pair<int, int> u;
if (low) {
u = v[l]; l++;
low = false;
}
else {
u = v[r]; r--;
low = true;
}
cout << u.first << " " << u.second << endl;
}
}
...
As the constraint is m*n<=10^6, this solution should work under 1 second but it's taking about 1871 ms in one of the TLE'd test case. Why could this be happening?
Name |
---|
add after declaring v.reserve(n*m);
I did it but its still slow..(1990 ms in custom test)
It is RTE, try "resize" instead of "reserve".
I tried both, still it takes around 1880 ms..
Now got it. Don't use "endl", use "\n" instead.
Works now. Thanks!
using "\n" instead makes that much of a difference ??
endl is write a newline and flush the stream. flush the stream each line take lot of time.
From the Competitive Programmer's Handbook, which I'm reading now: "Note that the newline "\n" works faster than endl, because endl always causes a flush operation."
If there are many lines in the output, then all these flushes may kill performance.
i see.. but my hands are set on endl.. we can always #define endl "\n" right ?
Until you face an interactive problem -> where you would need endl to flush the stream
For interactive problems,
'\n'
will also work because a read fromcin
forces to flushcout
, unlesscin.tie(0)
is used:For non-interactive problems
cin.tie(0)
should be used, to prevent the flush operations, in case there are some interleaving input and output operations.