team split, time limit exceed.

general
,
1

i have two implementation one is in c++ and one is in python.
c++ is working but python is not working(time limit exceed)

Team Split

c++ code:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
 
using namespace std;
 
#define MAX 100000
#define INF 2140000000
#define MOD 1000000007
 
int main() {
	#ifndef ONLINE_JUDGE
		freopen("in.txt","r",stdin);
	#endif	
	
	int test, n;
	long long a, b, c, d;
 
	cin >> test;
 
	while (test--) {
		int cnt[1000000] = {0};
		scanf("%d%lld%lld%lld%lld",&n,&a,&b,&c,&d);
 
		cnt[d]++;
 
		int maxi = d;
		int temp = d;
		for (int i = 1; i < n; ++i) {
			temp = (a*temp*temp + b*temp + c) % 1000000;
			cnt[temp]++;
			maxi = max(maxi, temp);
		}
 
		int ans = 0;
		bool check = 1;
 
		for (int i = maxi; i >= 0; --i) {
			if (check) {
				if (cnt[i]%2) {
					ans += i;
					check = !check;
				}
			}
			else {
				if (cnt[i]%2) {
					ans -= i;
					check = !check;
				}
			}
		}
 
		printf("%d\n",abs(ans));
	} 
	return 0;
}

here is python code:

import sys
import math
 
if __name__ == '__main__':
    t = int(sys.stdin.readline())
    for i in range(t):
        n,a,b,c,d = [int(u) for u in sys.stdin.readline().strip().split()]
        strip = [0] * 1000000
        strip[d] = 1
        max_val = d
        for k in range(1, n):
            d = ((a*d + b) * d + c) % 1000000
            strip[d] += 1
            max_val = max(max_val, d)
        ans = 0
        test = True
        for k in reversed(range(max_val+1)):
            if test:
                if strip[k] % 2 != 0:
                    ans += k
                    test = not test
            else:
                if strip[k] % 2 != 0:
                  ans -= k
                  test = not test
        print abs(ans)
2

The problem is generally not checked using all languages while being set, so sometimes predefined time limit may happen to be too strict for some languages. TMSLT has lot of TLE submissions and only 4 accepted in python. You can compare with them to find the required optimization.

1 Like
3

i think that python is not good for competitive programming contest. can you please suggest me that is it right ?