I use such an algorithm:
SumNeed - the last number in the input, what it's need to have
sum - the physical sum of all numbers
If ( SumNeed - sum ) does not divide by 9 - unrecoverable error.
Else ( SumNeed - sum ) / 9 is the difference between swapped digits. So I look through all the numbers, and if there are digits with difference ( SumNeed-sum )/9 - it is the mixed number.
On my computer when N=1500000 it works nearly 0.1 sec, and how it gets TLE - I can't even imagine. :(

[code cut]

Edited by moderator 16.03.2009 01:25

Use scanf()!
I had same problem. But now I have WA #45 :( Any hints? :)

The fastest one:
Don't read numbers as integers!
Read it as string or char[]
This way brings AC 0.18 sec

PS:
In such problems (input data is large and TL is small)
don't use scanf or cin to read integer numbers.

So, you think that the algorithm is good, but reading input takes all the time? Well, I will try to change, to read strings. Thanks!

Thanks to all, I have converted the algorithm into strings, now it is about 0.25 sec.
But - WA 45 :( I can't guess why. Is unsigned __int64 enough?
Burmistrov Ivan (USU), you told that you also had WA 45. Have you overcome this problem?

Now I have WA #46 :( In 45-th test correct number more than 2^31-1, I think. But what is 46-th test?

int64 is quite enough...

It's very strange!!!
Statement: "Each of the next N lines contains a corresponding non-negative integer summand (not exceeding 2^31-1)."
2^31 is 2147483648 - 10 symbols.
All input numbers I kept in char[11] and got WA.
When I changed the type into char[12] - I got Accepted!!!
How to explain it? ;)

!!! No question. My stupid fault :(

YES, AC 0.171 8-)

Edited by author 09.03.2006 17:22

I have WA #46 :( What's the problem??!

O, I think I undestood, what was wrong.
I had an array "long int a[1500000]", and other variables were __int64. When I corrected "__int64 a[1500000]", my program began to eat 12MB of memory instead of 6MB, but I got AC!!!!

Edited by author 10.03.2006 03:22

u are quite right!
i got AC this way,too!  Thx u for ur hints!
but does it mean the judge writer use number greater than 2^31-1? if yes, i have a feeling of being fooled!