Code Submission Evaluation System Login

Datatähti 2015 loppu

Start:2015-01-29 12:15:00
End:2015-01-29 17:15:00
 

Tasks | Scoreboard | Statistics


CSES - Datatähti 2015 loppu - Results
History
2015-01-29 15:52:12100
2015-01-29 15:43:1350
2015-01-29 15:39:3850
2015-01-29 15:35:2050
2015-01-29 15:32:2750
2015-01-29 14:55:4516
2015-01-29 13:34:0250
Task:Lukujono
Sender:Scintillo
Submission time:2015-01-29 15:52:12
Language:C++
Status:READY
Score:100

Feedback

groupverdictscore
#1ACCEPTED16
#2ACCEPTED34
#3ACCEPTED50

Test results

testverdicttime (s)group
#1ACCEPTED0.05 / 4.001details
#2ACCEPTED0.06 / 4.001details
#3ACCEPTED0.06 / 4.001details
#4ACCEPTED0.06 / 4.001details
#5ACCEPTED0.06 / 4.001details
#6ACCEPTED0.07 / 4.001details
#7ACCEPTED0.06 / 4.001details
#8ACCEPTED0.06 / 4.001details
#9ACCEPTED0.08 / 4.002details
#10ACCEPTED0.07 / 4.002details
#11ACCEPTED0.07 / 4.002details
#12ACCEPTED0.07 / 4.002details
#13ACCEPTED0.07 / 4.002details
#14ACCEPTED0.07 / 4.002details
#15ACCEPTED0.07 / 4.002details
#16ACCEPTED0.06 / 4.002details
#17ACCEPTED2.86 / 4.003details
#18ACCEPTED3.40 / 4.003details
#19ACCEPTED2.25 / 4.003details
#20ACCEPTED3.58 / 4.003details
#21ACCEPTED2.89 / 4.003details
#22ACCEPTED3.46 / 4.003details
#23ACCEPTED2.19 / 4.003details
#24ACCEPTED3.45 / 4.003details

Code

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <cassert>

using namespace std;
int x = 0;
//unordered_map<int, int64_t> cache;
const int cacheSize = 15463156;
int64_t cache[cacheSize];

int64_t solve(int i)
{
	if(i == 0 || i == 1)
		return i;

	if(cache[i % cacheSize])
		return cache[i % cacheSize];

	int64_t r = 0;

	vector<int> check;
	
	for(int monta = 1; monta <= i / 2;)
	{
		int suurin = i / monta;
		int pienin = i / (monta + 1) + 1;
		int kertaa = suurin - pienin + 1;

		/*if(i == x)
			cout << kertaa << " * solve " << monta << endl;*/


		r += kertaa * solve(monta);

		pienin -= 1;

		int a, b;
		a = monta;
		b = i / 2 + 2;

		while(a < b)
		{
			int c = (a + b) / 2;
			int res = i / c;

			if(res < pienin)
			{
				b = c;
			}
			else
			{
				a = c + 1;
			}
		}

		//cout << monta << endl;

		monta = b - 1;

		//cout << i << " " << pienin << " " << monta << endl;
	}

	return cache[i % cacheSize] = r;
}

int main()
{
	int n;
	cin >> n;
	//cache.reserve(100000);
	cout << solve(n) << endl;

	/*for(x = 2; x < 20; x++)
	{
		cout << "X: " << x << endl;
		solve(x);
		cout << endl;
	}*/
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
542

view   save

correct output
11942

view   save

user output
11942

view   save

Test 2

Group: 1

Verdict: ACCEPTED

input
929

view   save

correct output
29913

view   save

user output
29913

view   save

Test 3

Group: 1

Verdict: ACCEPTED

input
801

view   save

correct output
23460

view   save

user output
23460

view   save

Test 4

Group: 1

Verdict: ACCEPTED

input
935

view   save

correct output
30006

view   save

user output
30006

view   save

Test 5

Group: 1

Verdict: ACCEPTED

input
998

view   save

correct output
33766

view   save

user output
33766

view   save

Test 6

Group: 1

Verdict: ACCEPTED

input
942

view   save

correct output
30490

view   save

user output
30490

view   save

Test 7

Group: 1

Verdict: ACCEPTED

input
736

view   save

correct output
20285

view   save

user output
20285

view   save

Test 8

Group: 1

Verdict: ACCEPTED

input
930

view   save

correct output
29975

view   save

user output
29975

view   save

Test 9

Group: 2

Verdict: ACCEPTED

input
95404

view   save

correct output
90172356

view   save

user output
90172356

view   save

Test 10

Group: 2

Verdict: ACCEPTED

input
98060

view   save

correct output
94687572

view   save

user output
94687572

view   save

Test 11

Group: 2

Verdict: ACCEPTED

input
69495

view   save

correct output
52308390

view   save

user output
52308390

view   save

Test 12

Group: 2

Verdict: ACCEPTED

input
92197

view   save

correct output
85306979

view   save

user output
85306979

view   save

Test 13

Group: 2

Verdict: ACCEPTED

input
53418

view   save

correct output
32957881

view   save

user output
32957881

view   save

Test 14

Group: 2

Verdict: ACCEPTED

input
97377

view   save

correct output
93859995

view   save

user output
93859995

view   save

Test 15

Group: 2

Verdict: ACCEPTED

input
68065

view   save

correct output
50223001

view   save

user output
50223001

view   save

Test 16

Group: 2

Verdict: ACCEPTED

input
95463

view   save

correct output
90201672

view   save

user output
90201672

view   save

Test 17

Group: 3

Verdict: ACCEPTED

input
74323456

view   save

correct output
8975396101231

view   save

user output
8975396101231

view   save

Test 18

Group: 3

Verdict: ACCEPTED

input
92132055

view   save

correct output
13006378374515

view   save

user output
13006378374515

view   save

Test 19

Group: 3

Verdict: ACCEPTED

input
55135704

view   save

correct output
5354656932672

view   save

user output
5354656932672

view   save

Test 20

Group: 3

Verdict: ACCEPTED

input
98613338

view   save

correct output
14631125716007

view   save

user output
14631125716007

view   save

Test 21

Group: 3

Verdict: ACCEPTED

input
75558302

view   save

correct output
9238208186405

view   save

user output
9238208186405

view   save

Test 22

Group: 3

Verdict: ACCEPTED

input
94968034

view   save

correct output
13713914468591

view   save

user output
13713914468591

view   save

Test 23

Group: 3

Verdict: ACCEPTED

input
52163652

view   save

correct output
4858985762438

view   save

user output
4858985762438

view   save

Test 24

Group: 3

Verdict: ACCEPTED

input
94830583

view   save

correct output
13674294022172

view   save

user output
13674294022172

view   save