ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1510. Order

How to get <0.02 sec.?
Posted by Andrej Bourgasov 10 Sep 2019 13:22
Hey guys,
how to get run time under 0.02s?
I implement O(n) solution, but my time is ~0.15s for CLang...
What optimisations do you use?
Re: How to get <0.02 sec.?
Posted by Gilles Deleuze 10 Sep 2019 14:29
I used fast I/O to get 0.031. There are faster input methods that use fwrite/fread while mine is based on getChar/writeChar. Perhaps using even faster I/O can get you to 0.015


  int n = readUInt();
  int el = readUInt();
  int cnt = 1;
  for (int i = 1; i < n; ++i) {
    int x = readUInt();
    if (x == el) {
      ++cnt;
    } else {
      --cnt;
    }
    if (!cnt) {
      el = x;
      cnt = 1;
    }
  }
  writeInt(el);

Edited by author 10.09.2019 14:33
Re: How to get <0.02 sec.?
Posted by Gilles Deleuze 10 Sep 2019 14:44
And yes. I got accepted in 0.015s using fread/fwrite IO and C language compiler (not C++)