답안 #5215 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5215	2014-02-17T21:31:32 Z	tncks0121	생일수 II (GA4_birthday2)	C++	100 / 100	72 ms	6168 KB

birthday2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
 
using namespace std;
typedef long long ll;
const int INF = 987654321;
const ll LINF = (ll)1e15;
 
const int N = 200000;
const int N_ = N+10;
const ll MOD = 19980305;
 
struct mint {
    int v;
    mint(): v(0) { }
    mint(ll v): v((v+MOD*1000)%MOD) { }
     
    int operator*(){ return v; }
     
    mint operator+ (ll t) { return mint(v + t); }
    mint operator- (ll t) { return mint(v - t); }
    mint operator* (ll t) { return mint(v * t); }
    mint operator+ (mint t) { return mint(v + t.v); }
    mint operator- (mint t) { return mint(v - t.v); }
    mint operator* (mint t) { return mint((ll)v * t.v); }
};
 
mint operator+ (ll a, mint t) { return mint(a + t.v); }
mint operator- (ll a, mint t) { return mint(a - t.v); }
mint operator* (ll a, mint t) { return mint(a * t.v); }
 
mint E[N_];
mint A[N_], B[N_];
mint P3[N_], P10[N_];
mint T[N_];
char X[N_], Y[N_];
 
mint f (mint P, int n) {
    P = P * P10[n];
    mint ret = P3[n] - 1;
    ret = ret * P + B[n];
    ret = ret * P + T[n];
    return ret;
}
 
mint get (char *V) {
    int L = 0;
    mint ret, last, prefix;
     
    while(V[++L]); --L;
     
    for(int i = 1; i < L; i++) {
        ret = ret + last * (3 * E[i]) + T[i];
        last = 8 * E[i];
    }
     
    for(int i = 1; i <= L; i++) {
        if(V[i] >= '5') {
            mint low_prefix = prefix * 10 + 3;
            mint first = low_prefix * P10[L - i] + 3 * E[L - i];
            ret = ret + last * first + f(low_prefix, L - i);
            last = low_prefix * P10[L - i] + 8 * E[L - i];
        }
        if(V[i] >= '8') {
            mint low_prefix = prefix * 10 + 5;
            mint first = low_prefix * P10[L - i] + 3 * E[L - i];
            ret = ret + last * first + f(low_prefix, L - i);
            last = low_prefix * P10[L - i] + 8 * E[L - i];
        }
        prefix = prefix * 10 + (V[i] - '0');
    }
     
    ret = ret + last * prefix;
    return ret;
}
 
int main (){
    int i, j;
     
    P3[0] = P10[0] = 1;
    for(i = 1; i <= N; i++) {
        E[i] = E[i - 1] * 10 + 1;
        P3[i] = P3[i - 1] * 3;
        P10[i] = P10[i - 1] * 10;
        A[i] = A[i - 1] * 30 + 16 * P3[i - 1];
        B[i] = 2 * A[i] - 11 * E[i];
        T[i] = f(3, i - 1)
               + (3 * P10[i - 1] + 8 * E[i - 1]) * (5 * P10[i - 1] + 3 * E[i - 1]) + f(5, i - 1)
               + (5 * P10[i - 1] + 8 * E[i - 1]) * (8 * P10[i - 1] + 3 * E[i - 1]) + f(8, i - 1);
    }
     
    scanf("%s%s", X+1, Y+1);
     
    printf("%d\n", *(get(Y) - get(X)));
    return 0;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	6168 KB	Output is correct
2	Correct	32 ms	6168 KB	Output is correct
3	Correct	32 ms	6168 KB	Output is correct
4	Correct	32 ms	6168 KB	Output is correct
5	Correct	36 ms	6168 KB	Output is correct
6	Correct	36 ms	6168 KB	Output is correct
7	Correct	32 ms	6168 KB	Output is correct
8	Correct	32 ms	6168 KB	Output is correct
9	Correct	32 ms	6168 KB	Output is correct
10	Correct	28 ms	6168 KB	Output is correct
11	Correct	36 ms	6168 KB	Output is correct
12	Correct	32 ms	6168 KB	Output is correct
13	Correct	32 ms	6168 KB	Output is correct
14	Correct	32 ms	6168 KB	Output is correct
15	Correct	32 ms	6168 KB	Output is correct
16	Correct	28 ms	6168 KB	Output is correct
17	Correct	28 ms	6168 KB	Output is correct
18	Correct	28 ms	6168 KB	Output is correct
19	Correct	36 ms	6168 KB	Output is correct
20	Correct	32 ms	6168 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	6168 KB	Output is correct
2	Correct	32 ms	6168 KB	Output is correct
3	Correct	32 ms	6168 KB	Output is correct
4	Correct	36 ms	6168 KB	Output is correct
5	Correct	32 ms	6168 KB	Output is correct
6	Correct	32 ms	6168 KB	Output is correct
7	Correct	28 ms	6168 KB	Output is correct
8	Correct	28 ms	6168 KB	Output is correct
9	Correct	32 ms	6168 KB	Output is correct
10	Correct	32 ms	6168 KB	Output is correct
11	Correct	28 ms	6168 KB	Output is correct
12	Correct	32 ms	6168 KB	Output is correct
13	Correct	32 ms	6168 KB	Output is correct
14	Correct	32 ms	6168 KB	Output is correct
15	Correct	36 ms	6168 KB	Output is correct
16	Correct	36 ms	6168 KB	Output is correct
17	Correct	32 ms	6168 KB	Output is correct
18	Correct	32 ms	6168 KB	Output is correct
19	Correct	28 ms	6168 KB	Output is correct
20	Correct	28 ms	6168 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	6168 KB	Output is correct
2	Correct	36 ms	6168 KB	Output is correct
3	Correct	32 ms	6168 KB	Output is correct
4	Correct	36 ms	6168 KB	Output is correct
5	Correct	32 ms	6168 KB	Output is correct
6	Correct	32 ms	6168 KB	Output is correct
7	Correct	32 ms	6168 KB	Output is correct
8	Correct	36 ms	6168 KB	Output is correct
9	Correct	36 ms	6168 KB	Output is correct
10	Correct	36 ms	6168 KB	Output is correct
11	Correct	32 ms	6168 KB	Output is correct
12	Correct	32 ms	6168 KB	Output is correct
13	Correct	36 ms	6168 KB	Output is correct
14	Correct	36 ms	6168 KB	Output is correct
15	Correct	32 ms	6168 KB	Output is correct
16	Correct	32 ms	6168 KB	Output is correct
17	Correct	32 ms	6168 KB	Output is correct
18	Correct	32 ms	6168 KB	Output is correct
19	Correct	32 ms	6168 KB	Output is correct
20	Correct	32 ms	6168 KB	Output is correct

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	64 ms	6168 KB	Output is correct
2	Correct	64 ms	6168 KB	Output is correct
3	Correct	72 ms	6168 KB	Output is correct
4	Correct	64 ms	6168 KB	Output is correct
5	Correct	64 ms	6168 KB	Output is correct
6	Correct	64 ms	6168 KB	Output is correct
7	Correct	68 ms	6168 KB	Output is correct
8	Correct	72 ms	6168 KB	Output is correct
9	Correct	64 ms	6168 KB	Output is correct
10	Correct	68 ms	6168 KB	Output is correct
11	Correct	64 ms	6168 KB	Output is correct
12	Correct	72 ms	6168 KB	Output is correct
13	Correct	64 ms	6168 KB	Output is correct
14	Correct	64 ms	6168 KB	Output is correct
15	Correct	72 ms	6168 KB	Output is correct
16	Correct	64 ms	6168 KB	Output is correct
17	Correct	72 ms	6168 KB	Output is correct
18	Correct	68 ms	6168 KB	Output is correct
19	Correct	60 ms	6168 KB	Output is correct
20	Correct	72 ms	6168 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	6168 KB	Output is correct
2	Correct	72 ms	6168 KB	Output is correct
3	Correct	64 ms	6168 KB	Output is correct
4	Correct	72 ms	6168 KB	Output is correct
5	Correct	68 ms	6168 KB	Output is correct
6	Correct	72 ms	6168 KB	Output is correct
7	Correct	72 ms	6168 KB	Output is correct
8	Correct	68 ms	6168 KB	Output is correct
9	Correct	68 ms	6168 KB	Output is correct
10	Correct	68 ms	6168 KB	Output is correct
11	Correct	60 ms	6168 KB	Output is correct
12	Correct	72 ms	6168 KB	Output is correct
13	Correct	72 ms	6168 KB	Output is correct
14	Correct	72 ms	6168 KB	Output is correct
15	Correct	68 ms	6168 KB	Output is correct
16	Correct	52 ms	6168 KB	Output is correct
17	Correct	48 ms	6168 KB	Output is correct
18	Correct	44 ms	6168 KB	Output is correct
19	Correct	52 ms	6168 KB	Output is correct
20	Correct	52 ms	6168 KB	Output is correct

답안 #5215

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 15.0 / 15.0

Subtask #3 20.0 / 20.0

Subtask #4 25.0 / 25.0

Subtask #5 30.0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
15.0 / 15.0

Subtask #3
20.0 / 20.0

Subtask #4
25.0 / 25.0

Subtask #5
30.0 / 30.0