oj.uz

Submission #612537

# Submission time Handle Problem Language Result Execution time Memory
612537 2022-07-29T17:07:16 Z karelisp Kpart (eJOI21_kpart) C++14
0 / 100
 2000 ms 736 KB 
#include <bits/stdc++.h>
using namespace std;

int T, N, a[1005], ps[1005];

int main(){
	scanf("%d", &T);
	while(T--){
		vector<int> emf(100005);
		scanf("%d", &N);

		for(int i=1; i<=N; i++){
			scanf("%d", &a[i]);
			ps[i] = ps[i-1] + a[i];
		}

		vector<int> ans;
		for(int K=2; K<=N; K++){
			bitset<100005> sums;
			bitset<100005> cur_window;
			sums[0] = true;
			cur_window[0] = true;
			bool is_Kary = true;
			for(int right=1; right<=N && is_Kary; right++){
				emf[a[right]]++;
				cur_window[a[right]] = true;
				sums |= sums<<a[right];
				if(right<K) 
					continue;

				int cur_sum = ps[right] - ps[right-K];
				if(cur_sum%2 || sums[cur_sum/2]==0){
					is_Kary = false;
				}
				
				emf[a[right-K+1]]--;
				if(emf[a[right-K+1]] == 0)
					cur_window[a[right]] = false;
				sums = sums>>a[right];
				sums |= cur_window;
			}
			
			if(is_Kary)
				ans.push_back(K);
		}

		printf("%ld ", ans.size());
		for(auto K : ans) printf("%d ", K);
		printf("\n");
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:7:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  scanf("%d", &T);
      |  ~~~~~^~~~~~~~~~
Main.cpp:10:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |   scanf("%d", &N);
      |   ~~~~~^~~~~~~~~~
Main.cpp:13:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |    scanf("%d", &a[i]);
      |    ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 147 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 736 KB Time limit exceeded
2 Halted 0 ms 0 KB -