CSES - Harjoituskisa 7.1.2018

CSES - Harjoituskisa 7.1.2018 - Results

Submission details
Task:	Keskiarvot
Sender:	Kuha
Submission time:	2018-01-07 19:32:45 +0200
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	12
#2	ACCEPTED	17
#3	ACCEPTED	71

Test results
test	verdict	time	group
#1	ACCEPTED	0.04 s	1	details
#2	ACCEPTED	0.05 s	1	details
#3	ACCEPTED	0.05 s	1	details
#4	ACCEPTED	0.05 s	1	details
#5	ACCEPTED	0.05 s	1	details
#6	ACCEPTED	0.05 s	2	details
#7	ACCEPTED	0.05 s	2	details
#8	ACCEPTED	0.05 s	2	details
#9	ACCEPTED	0.04 s	2	details
#10	ACCEPTED	0.03 s	2	details
#11	ACCEPTED	0.07 s	3	details
#12	ACCEPTED	0.07 s	3	details
#13	ACCEPTED	0.06 s	3	details
#14	ACCEPTED	0.08 s	3	details
#15	ACCEPTED	0.08 s	3	details

Code

#include <bits/stdc++.h>

#define N (1<<17)
#define ll long long
#define ld long double
#define M 1000000007
#define INF 0x5ADFACE5
#define LINF 0x51DEEFFEC7C0DECALL
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second

using namespace std;

ll v[111111];
ll s[111111];
ll sz[111111];

ll gs (ll a, ll b) {
	if (a == 0) return s[b];
	return s[b] - s[a - 1];
}

int main () {
	cin.sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	for (int i = 0; i < n; i++) cin>>v[i];
	for (int i = 0; i < n; i++) {
		s[i] = v[i];
		if (i) s[i] += s[i - 1];
	}
	for (int i = 0; i < n; i++) {
		sz[i] = 1;
		int j = i - 1;
		while (j >= 0) {
			// s_1 / n_1 <= s_2 / n_2 <=> s_1n_2 <= s_2n_1
			if (gs(j + 1, i) * (sz[i] + sz[j]) <= gs(i - sz[i] - sz[j] + 1, i) * sz[i]) {
				sz[i] += sz[j];
				j = i - sz[i];
			} else break;
		}
		cout<<sz[i]<<" ";
	}
	cout<<endl;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
`100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

Test 2

Group: 1

Verdict: ACCEPTED

input
`100 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

Test 3

Group: 1

Verdict: ACCEPTED

input
`100 1000000 999999 999998 999997 9...` view save

correct output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

Test 4

Group: 1

Verdict: ACCEPTED

input
`100 4 1 6 9 4 793899 5 5 8 7 5 4 7...` view save

correct output
`1 2 1 1 2 1 2 3 4 5 6 7 8 9 10...` view save

user output
`1 2 1 1 2 1 2 3 4 5 6 7 8 9 10...` view save

Test 5

Group: 1

Verdict: ACCEPTED

input
`100 442147 824215 62008 513740 542...` view save

correct output
`1 1 2 1 1 3 1 2 6 10 11 12 1 1...` view save

user output
`1 1 2 1 1 3 1 2 6 10 11 12 1 1...` view save

Test 6

Group: 2

Verdict: ACCEPTED

input
`5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

Test 7

Group: 2

Verdict: ACCEPTED

input
`5000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

Test 8

Group: 2

Verdict: ACCEPTED

input
`5000 1000000 999999 999998 999997 9...` view save

correct output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

Test 9

Group: 2

Verdict: ACCEPTED

input
`5000 7 5 6 1 9 1 1 6 10 8 7 4 7 1 1...` view save

correct output
`1 2 3 4 1 2 7 1 1 2 3 4 5 6 1 ...` view save

user output
`1 2 3 4 1 2 7 1 1 2 3 4 5 6 1 ...` view save

Test 10

Group: 2

Verdict: ACCEPTED

input
`5000 236071 202283 94200 149202 642...` view save

correct output
`1 2 3 4 1 1 2 3 5 1 2 1 9 10 1...` view save

user output
`1 2 3 4 1 1 2 3 5 1 2 1 9 10 1...` view save

Test 11

Group: 3

Verdict: ACCEPTED

input
`100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

Test 12

Group: 3

Verdict: ACCEPTED

input
`100000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

Test 13

Group: 3

Verdict: ACCEPTED

input
`100000 1000000 999999 999998 999997 9...` view save

correct output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

Test 14

Group: 3

Verdict: ACCEPTED

input
`100000 4 10 3 2 235575 7 374394 4 4 5...` view save

correct output
`1 1 2 3 1 2 1 2 3 6 7 8 9 10 1...` view save

user output
`1 1 2 3 1 2 1 2 3 6 7 8 9 10 1...` view save

Test 15

Group: 3

Verdict: ACCEPTED

input
`100000 243549 902542 256118 941342 41...` view save

correct output
`1 1 2 1 2 5 6 1 8 9 1 2 12 13 ...` view save

user output
`1 1 2 1 2 5 6 1 8 9 1 2 12 13 ...` view save

Harjoituskisa 7.1.2018

Keskiarvot

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Tasks

Submissions (Kuha)