Submission #7196379


Source Code Expand

Copy
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define pii std::pair<int,int>
#define pli std::pair<ll,int>
#define pil std::pair<int,ll>
#define psi std::pair<string,int>
#define pll std::pair<ll,ll>
#define pci std::pair<char,int>
#define sll(x) scanf("%lld",&x)
#define prll(x) printf("%lld ",x)
#define pri(x) printf("%d ",x)
#define si(x) scanf("%d",&x)
#define pb push_back
#define vll std::vector<ll>
#define vpi std::vector<std::pair<int,int>>
#define vi std::vector<int>
#define vvi std::vector<std::vector<int>>
#define vvpil std::vector<std::vector<std::pair<int,ll>>>
#define vlpii std::vector<std::list<pii>>
#define vlpil std::vector<std::list<pil>>
#define li std::list<int>
#define lpil std::list<pil>
#define Endl printf("\n")
#define vli vector<list<int>>
#define vvll vector<vector<ll>>
#define mp make_pair
#define x first
#define y second
#define ull uint64_t
#define ma 100000000
#define imie(...) "[" << #__VA_ARGS__": " << (__VA_ARGS__) << "] "
const ll  INF=10000000000000;
const ll mod =  1e9 + 7;
using namespace std;
void add(ll& a , ll b){
	a += b;
	if(a >= mod) a -= mod;
}
ll mul(ll a , ll b){
	return (a * b) % mod;
}
ll Pow(ll a , ll b){
	if(b == 0) return 1 ;
	ll c = Pow(a , b / 2) ;
	if(b % 2) return (a * ((c * c)% mod )) % mod ;
	return (c * c) % mod ;
}
int verif(string s){
	int val = 0 ;
	bool b = true ;
	for(int i = 0 ; i < (int)s.size() ; i++){
		if(s[i] == '?'){
			b = false;
			for(int j = 0 ; j < 10 ; j++){
				s[i] = (char)(j + (int)'0') ;
				val += verif(s) ;
			}
			break ;
		}
	}
	if(b){
		ll x = atoll(s.c_str()) ;
		return (x % 13 == 5) ;
	}
	return val ;
}
ll Mod(ll x){
	while(x < 0) x += 13 ;
	return x % 13 ;
}
//check modulo
int main(){
	IOS;
	cout.precision(30) ;
	string s ; cin >> s ;
	//cout << verif(s) << endl ;
	if(s.size() % 3 == 1) s = "00" + s ;
	if(s.size() % 3 == 2) s = "0" + s ;	
	int n = s.size() ;
	ll cur = 0 ;
	for(int i = 0 ; i < n ; i++){
		if(s[i] != '?'){
			if(i % 6 == 0) cur += 100 * ((int)s[i] - (int)'0') ;
			if(i % 6 == 1) cur += 10 * ((int)s[i] - (int)'0') ;
			if(i % 6 == 2) cur += 1 * ((int)s[i] - (int)'0') ;
			if(i % 6 == 3) cur += -100 * ((int)s[i] - (int)'0') ;
			if(i % 6 == 4) cur += -10 * ((int)s[i] - (int)'0') ;
			if(i % 6 == 5) cur += -1 * ((int)s[i] - (int)'0') ;
		}
	}
	while(cur < 0) cur += 13 ;
	vll dp(13 , 0) ;
	dp[cur % 13] = 1 ;
	for(int i = 0 ; i < n ; i++){
		if(s[i] =='?'){
			ll m ;
			if(i % 6 == 0) m = 100 ;
			if(i % 6 == 1) m = 10 ;
			if(i % 6 == 2) m = 1 ;
			if(i % 6 == 3) m = -100 ;
			if(i % 6 == 4) m = -10 ;
			if(i % 6 == 5) m = -1 ;
			vector<vll> tmp (10 , vll(13 , 0)) ;
			tmp[0] = dp ;
			for(int j = 1 ; j < 10 ; j++){
				for(int k = 0 ; k < 13 ; k++){
					add(tmp[j][Mod(m * j + k)] , dp[k]) ;
				}
			}
			for(int k = 0 ; k < 13 ; k++){
				for(int j = 1 ; j < 10 ; j++){
					add(dp[k] , tmp[j][k]) ;
				}
			}
		}
	}
	cout << dp[5] << endl ; 
			
	return 0;
}

Submission Info

Submission Time
Task D - Digits Parade
User Haykel
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3091 Byte
Status WA
Exec Time 153 ms
Memory 512 KB

Judge Result

Set Name Sample Subtask1
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
WA × 1
AC × 21
WA × 9
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 384 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt WA 1 ms 256 KB
sub1_01.txt AC 51 ms 384 KB
sub1_02.txt AC 71 ms 384 KB
sub1_03.txt WA 1 ms 256 KB
sub1_04.txt WA 1 ms 256 KB
sub1_05.txt AC 59 ms 384 KB
sub1_06.txt AC 2 ms 256 KB
sub1_07.txt WA 2 ms 256 KB
sub1_08.txt WA 15 ms 512 KB
sub1_09.txt AC 141 ms 512 KB
sub1_10.txt AC 100 ms 384 KB
sub1_11.txt AC 2 ms 256 KB
sub1_12.txt AC 2 ms 256 KB
sub1_13.txt AC 1 ms 256 KB
sub1_14.txt AC 1 ms 256 KB
sub1_15.txt AC 1 ms 256 KB
sub1_16.txt AC 1 ms 256 KB
sub1_17.txt AC 153 ms 512 KB
sub1_18.txt WA 47 ms 512 KB
sub1_19.txt WA 122 ms 512 KB
sub1_20.txt WA 125 ms 512 KB
sub1_21.txt AC 2 ms 512 KB
sub1_22.txt AC 2 ms 512 KB
sub1_23.txt AC 2 ms 512 KB
sub1_24.txt WA 122 ms 512 KB
sub1_25.txt AC 1 ms 256 KB
sub1_26.txt AC 1 ms 256 KB