Pedrams's blog

By Pedrams, 10 years ago, In English

Hi everyone.

I saw a code in the "Status" tab today, which made me wonder: <<How does it work in less than 2 seconds?>> Its number of operations was about (5 * 10^9)...

So my question is: How many operations can exactly be done in 1 second, here in Codeforces?

To be more clear, this is the problem: 287B - Трубопровод And this is the submission: 4075576

(1 ≤ n ≤ 10^18, 2 ≤ k ≤ 10^9) * see test #4 * the answer is (-1), so we are sure that k reaches 0

Recently, I wrote two codes for this problem. Code #1 gets "Time limit exceeded" while code #2 gets "Accepted". What's the differences which cause this problem?

// code #1
#include <bits/stdc++.h>
using namespace std;
	
typedef long long LL;
LL n, k;
LL sum, ans;

int main()
{
    ios::sync_with_stdio(false);
    freopen("B.in", "r", stdin);
    n = 1e18;
    k = 1e9;
    sum = 1;
    while(--k && sum < n)
    {
        sum += k;
        ans++;
    }
    if(sum < n)
        cout << -1 << endl;
    else
        cout << ans << endl;
		
    return 0;
}
// code #2 -- equal to the submission I said.
#include<stdio.h>
int main()
{
    __int64 n,res=1;
    int k,ans=0;
    scanf("%I64d %d",&n,&k);
    while(res<n&&k>=2)
    {
        --k;
        res+=k;
        ++ans;
    }
    printf("%d\n",res>=n? ans: -1);
    return 0;
}

** Even when I write this code at the end of both of them, surprisingly code #1 shows something about 3.5 seconds and code #2 shows something about 4 seconds!! cout << (double)clock()/CLOCKS_PER_SEC << endl;

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it