CSES - Putka Open 2015 – 5/6 - Results
Submission details
Task:Käännöt
Sender:Henrik Lievonen
Submission time:2015-11-07 19:19:47 +0200
Language:C++
Status:READY
Result:56
Feedback
groupverdictscore
#1ACCEPTED15
#2ACCEPTED41
#30
Test results
testverdicttimegroup
#1ACCEPTED0.07 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.05 s1details
#6ACCEPTED0.06 s2details
#7ACCEPTED0.05 s2details
#8ACCEPTED0.05 s2details
#9ACCEPTED0.07 s2details
#10ACCEPTED0.06 s2details
#11--3details
#12--3details
#13--3details
#14--3details
#15--3details

Code

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <array>

using namespace std;

typedef long long int ll;

const ll M = 1000000007;
struct modnum {
	ll val;
	modnum(ll val) :val(val%M) {}
	modnum() :val(0) {}

	modnum &operator+=(const modnum &o) {
		val = (val + o.val) % M;
		return *this;
	}
	modnum operator+(const modnum &o) {
		modnum r = *this;
		r += o;
		return r;
	}
	modnum &operator*=(const modnum &o) {
		val = (val * o.val) % M;
		return *this;
	}
	modnum operator*(const modnum &o) {
		modnum r = *this;
		r *= o;
		return r;
	}

	operator ll() const {
		return val;
	}
};
typedef modnum mn;

mn powmod(mn b, ll e) {
	if (e == 0)
		return 1;
	if (e == 1)
		return b;
	if (e % 2 == 0) {
		mn p = powmod(b, e / 2);
		return p*p;
	}
	return powmod(b, e / 2)*powmod(b, e / 2 + 1);
}

const size_t S = 1024 * 128;
struct seqtree {
	vector<mn> tree;

	seqtree() : tree(2 * S) {}

	void rawset(size_t i, mn val) {
		tree[S + i] = val;
	}
	void rawbuild() {
		for (int i = S - 1; i >= 0; i--)
			tree[i] = tree[2 * i] + tree[2 * i + 1];
	}
	mn get(size_t a, size_t b) const {
		a += S;
		b += S;
		mn r;
		while (a < b) {
			if (a % 2 == 1)r += tree[a], a++;
			if (b % 2 == 0)r += tree[b], b--;
			a /= 2;
			b /= 2;
		}
		if (a == b)
			r += tree[a];
		return r;
	}
};

ll dojob(const string &s) {
	typedef seqtree SEQ_T;
	SEQ_T *seq_p = new SEQ_T();
	SEQ_T &seq = *seq_p;

	const ll sl = s.length();

	// Build seqment tree
	{
		for (int i = sl - 1; i >= 0; i--)
			seq.rawset(i, mn(s[i] - '0'));
		seq.rawbuild();
	}

	mn res = 0;
	// Add base grid
	{
		mn add = 0;
		for (int i = 0; i < sl / 2; i++) {
			add += seq.get(i, sl - i - 1);
			res += add*powmod(mn(10), i);
			res += add*powmod(mn(10), sl - i - 1);
		}
		if (sl % 2 != 0) {
			add += seq.get(sl / 2, sl / 2);
			res += add*powmod(mn(10), sl / 2);
		}
	}

	// Add diagonal
	{
		ll mul = sl*(sl - 1) / 2;
		ll sub = sl - 3;
		if (sub < 0) sub = 0;
		for (int i = 0; i < sl / 2; i++) {
			res += seq.get(i, i) * mn(mul) * powmod(mn(10), sl - i - 1);
			res += seq.get(sl - i - 1, sl - i - 1) * mn(mul) * powmod(mn(10), i);

			mul -= sub;
			sub -= 2;
			if (sub < 0) sub = 0;
			mul -= 1;
			//add += seq.get(i, sl - i - 1);
			//res += mn(2)*add;
		}
		if (sl % 2 != 0) {
			res += seq.get(sl / 2, sl / 2) * mn(mul) * powmod(mn(10), sl / 2);
		}
	}

	delete seq_p;

	return res;
}


int main() {
	string s;
	cin >> s;
	cout << dojob(s) << endl;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
825864589849478186996872119675...

correct output
457966376

user output
457966376

Test 2

Group: 1

Verdict: ACCEPTED

input
191658935877461356157657491987...

correct output
176954270

user output
176954270

Test 3

Group: 1

Verdict: ACCEPTED

input
348988594526165698179722696175...

correct output
338693404

user output
338693404

Test 4

Group: 1

Verdict: ACCEPTED

input
959161872742625799336943933597...

correct output
585928712

user output
585928712

Test 5

Group: 1

Verdict: ACCEPTED

input
925429363246698689162197257943...

correct output
517617697

user output
517617697

Test 6

Group: 2

Verdict: ACCEPTED

input
972591294933975999938266397628...

correct output
667001154

user output
667001154

Test 7

Group: 2

Verdict: ACCEPTED

input
275688881195265674233697529772...

correct output
213272855

user output
213272855

Test 8

Group: 2

Verdict: ACCEPTED

input
654678934762543351831648468742...

correct output
465477034

user output
465477034

Test 9

Group: 2

Verdict: ACCEPTED

input
852895263384279396767531876338...

correct output
225052500

user output
225052500

Test 10

Group: 2

Verdict: ACCEPTED

input
257723665884149498894428498943...

correct output
169577498

user output
169577498

Test 11

Group: 3

Verdict:

input
965391619923528543348143963721...

correct output
458795777

user output
(empty)

Test 12

Group: 3

Verdict:

input
934996116481518541954869782274...

correct output
38884659

user output
(empty)

Test 13

Group: 3

Verdict:

input
356521595763548549682719476371...

correct output
335143519

user output
(empty)

Test 14

Group: 3

Verdict:

input
691571977153731228387836644955...

correct output
504860195

user output
(empty)

Test 15

Group: 3

Verdict:

input
882254176987218851832315176774...

correct output
32749477

user output
(empty)