Submission #22893

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22893	2017-04-30T09:11:01 Z	pichulia	Unifying Values (KRIII5_UV)	C++	0 / 7	29 ms	3408 KB

UV

#include<stdio.h>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;
#define I 16384
#define M 1000000007
typedef pair<long long int, int> pii;
int n;
long long int a[10009];
long long int s[10009];
long long int res;
map<long long int, vector<int> > xx;
set<long long int> ss;
long long int ms[2 * I];
void update_ms(int i, long long int k) {
	ms[i + I] = k%M;
	i = i + I;
	i /= 2;
	while (i > 0) {
		ms[i] = (ms[i * 2] + ms[i * 2 + 1]) % M;
		i /= 2;
	}
}
long long int get_ms(int dep, int ql, int qr, int ll, int rr) {
	if (rr < ql || qr < ll) return 0;
	if (ql <= ll && rr <= qr) { return ms[dep]; }
	return (get_ms(dep * 2, ql, qr, ll, (ll + rr) / 2) + get_ms(dep * 2 + 1, ql, qr, (ll + rr) / 2 + 1, rr)) % M;
}
void process(long long int x) {
	int i, j, k, l;
	long long int m;
	if (s[n] == 0) m = -1;
	else {
		m = s[n] / x;
		if (m > n) return;
		if (m < 2) return;
	}
	int cur, nxt;
	cur = 0; nxt = 1;
	int si = n+2;
	for (i = 0; i < 2 * I; i++)
		ms[i] = 0;
	for (i = 1; i <= n; i++)
	{
		if (s[i] == x)
		{
			update_ms(i, 1);
		}
	}
	if (m > 1) {
		xx.clear();
		for (i = 1; i <= n; i++) {
			if (s[i] % x == 0 && s[i]/x>0) {
				xx[s[i]].push_back(i);
			}
		}
		for (k = 2; k <= m; k++) {
			long long int cur = k*x;
			for (i = ((int)xx[cur].size()) - 1; i >= 0; i--) {
				long long int kk = get_ms(1, 0, xx[cur][i], 0, I - 1);
				update_ms(xx[cur][i], kk);
			}
			for (i = ((int)xx[cur-x].size()) - 1; i >= 0; i--) {
				update_ms(xx[cur-x][i], 0);
			}
		}
		res = (res + ms[n + I]);
	}
	else
	{
		int ss = 0;
		for (i = 1; i < n; i++) { if (s[i] == 0)ss++; }
		res = 1;
		for (i = 0; i < ss; i++) { res = (res * 2) % M; }
		res = (res - 1 + M) % M;
	}
}
int main() {
	int i, j, k, l;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		s[i] = s[i - 1] + a[i];
	}
	res = 0;
	for (i = 1; i < n; i++) {
		if (s[n] == 0 && s[i] == 0) {
			if (ss.find(s[i]) != ss.end()) continue;
			ss.insert(s[i]);
			process(0);
		}
		else if (s[i] != 0 && s[n] % s[i] == 0 && s[n] / s[i] > 1) {
			if (ss.find(s[i]) != ss.end()) continue;
			ss.insert(s[i]);
			process(s[i]);
		}
	}
	printf("%lld\n", res);
	return 0;
}

Compilation message

UV.cpp: In function 'void process(long long int)':
UV.cpp:32:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k, l;
         ^
UV.cpp:32:15: warning: unused variable 'l' [-Wunused-variable]
  int i, j, k, l;
               ^
UV.cpp:40:6: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
  int cur, nxt;
      ^
UV.cpp:40:11: warning: variable 'nxt' set but not used [-Wunused-but-set-variable]
  int cur, nxt;
           ^
UV.cpp:42:6: warning: unused variable 'si' [-Wunused-variable]
  int si = n+2;
      ^
UV.cpp: In function 'int main()':
UV.cpp:81:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k, l;
         ^
UV.cpp:81:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k, l;
            ^
UV.cpp:81:15: warning: unused variable 'l' [-Wunused-variable]
  int i, j, k, l;
               ^
UV.cpp:82:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
UV.cpp:84:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
                       ^

Subtask #1

0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2352 KB	Output is correct
2	Correct	0 ms	2352 KB	Output is correct
3	Correct	0 ms	2352 KB	Output is correct
4	Correct	29 ms	3408 KB	Output is correct
5	Correct	23 ms	3408 KB	Output is correct
6	Correct	0 ms	2352 KB	Output is correct
7	Incorrect	13 ms	2616 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2

0 / 5.0

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