Блог пользователя mihir

Автор mihir, 9 лет назад, По-английски

Hi, yesterday, I was solving a problem from the IARCS judge and my solution was accepted for all the test cases except one. For that particular test case, the output was SIGABRT error. I tried to figure out why I was getting this error but to no avail. If you can figure out why I am getting this error then please let me know.

The link to the problem — Problem

My solution to the problem —

#include<bits/stdc++.h>
 
using namespace std;

#define ll long long
 
int main()
{
    ll N, K;
    cin>>N>>K;
    
    set< ll int> S;
    
    while(K-- )
    {
        ll X;
        cin>>X;
        
        for(int i=1; i<=N; i = i + X)
        {
            S.insert(i);
        }
    }
    
    cout<<N - S.size();
}

My solution was failing the 7th test case to the problem. The test cases for the problem can be found over here — Testcases This solution worked fine for the 7th test case when I tried it on codechef's IDE and codeforces custom test.

My solution was failing the 7th test case only due to which I only managed to get 90/100 for this problem. If you can point out the mistake in my solution and let me know about it then I would appreciate your help.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Well, I assume that the worst case scenario is that you have N = 1e+9, K = 20 and each caterpillar has the lenght of 1. If so, your solution will make 20 * 1e+9 * log(1e+9) operations, which is very slow, so it have to fail because of TL.