oj.uz

Submission #845511

# Submission time Handle Problem Language Result Execution time Memory
845511 2023-09-06T13:57:03 Z vjudge1 Trener (COCI20_trener) C++17
110 / 110
 1534 ms 23304 KB 
// Imagine not FFT
#include <bits/stdc++.h>
#define ONLINE_JUDGE
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
#ifndef ONLINE_JUDGE
    #define DEBUG(x) std::cerr << #x << ": " << x << std::endl;
    #define DEBUGV(x) std::cerr << #x << ": { "; for(auto ___y:x) std::cerr << ___y << " "; std::cerr << "}" << std::endl;
    #define DEBUGVV(x) std::cerr << #x << ": { \n"; for(int _i=0;_i<sz(x);++_i) {DEBUGV(x[_i]);} std::cerr << "}" << std::endl;
	#define DEBUGVP(x) std::cerr << #x << ": { "; for(auto ___y:x) std::cerr << "{" << ___y.first << "," << ___y.second << "}" << " "; std::cerr << "}" << std::endl;
	#define DEBUGPII(x) std::cerr << #x << ": { " << x.first << " , " << x.second << " }" << endl;
	#define files freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
    #define fastio std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);
#else
    #define fastio std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);
    #define DEBUG(...) void(23)
    #define DEBUGV(x) void(23);
    #define DEBUGARR(arr, size) void(23)
    #define DEBUGPRINT(...) void(23)
    #define DEBUGMAP(...) void(23)
    #define DEBUGMAPQUEUE(...) void(23)
    #define DEBUGVV(x) void(23);
    #define DEBUGVP(x) void(23);
	#define DEBUGPII(x) void(23);
    #define files void(23);
#endif

#define int long long
#define ll long long
 
#define pb push_back
#define ff first
#define ss second
#define pii std::pair < int , int >
#define pll std::pair < ll , ll >
#define vi std::vector < ll >
#define vl std::vector < int >
#define vii std::vector < pii >
#define vll std::vector < pll >
#define vvi std::vector < vi >
#define vvii std::vector < vii >
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define forn(i,j) for(int i=0;i<j;i++)
#define forr(i,j,k) for(int i=j;i<k;i++)
 
#define mset multiset
#define pqueue priority_queue
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))
 
#define sz(a) (int)(a.size())
     
const int MOD = 1000000007;
const int MOD2 = 998244353;

using namespace std;

bool isSub(string a, string b){
	if((b[0]+a)==b) return true;
	if((a+b[sz(b)-1])==b) return true;
	return false;
}

int add(int a, int b){
	return (a+b)%MOD;
}

int addd(int& a, int b){
	return (a=((a+b)%MOD));
}

unordered_map < string , int > c,cy,cr;

void solve(int _t_case){
	int n,k;
	forn(i,26){
		string s="a";
		s[0]+=i;
		c[s]=1;
	}
	cin >> n >> k;
	vector < int > a;
	forn(i,n){
		forn(j,k){
			string sur;
			cin >> sur;
			if(i+1<n && c[sur]>0){
				int thi=c[sur];
				for(int __i_=0;__i_<26;__i_++){
					addd(cy[(char(__i_+'a'))+sur],thi);
					if(((char(__i_+'a'))+sur)!=(sur+(char(__i_+'a')))) addd(cy[sur+(char(__i_+'a'))],thi);
				}
			}
			if(i+1==n && c[sur]>0) a.pb(c[sur]);
		}
		if(true || i+1!=n){
			c=cy;
			cy=cr;
			DEBUGVP(c);
			DEBUGVP(cy);
		}
	}
	DEBUGVP(c);
	int ans = 0;
	for(auto _a:a) addd(ans,_a);
	cout << ans << endl;
	return;
}

signed main(){
    fastio;
    files;
    int t=1,_t=0;
    //std::cin >> t;
    while(_t<t){
        ++_t;
        solve(_t);
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1524 KB Output is correct
2 Correct 58 ms 1928 KB Output is correct
3 Correct 59 ms 2212 KB Output is correct
4 Correct 26 ms 348 KB Output is correct
5 Correct 51 ms 1556 KB Output is correct
6 Correct 52 ms 1632 KB Output is correct
7 Correct 27 ms 348 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 55 ms 1524 KB Output is correct
6 Correct 58 ms 1928 KB Output is correct
7 Correct 59 ms 2212 KB Output is correct
8 Correct 26 ms 348 KB Output is correct
9 Correct 51 ms 1556 KB Output is correct
10 Correct 52 ms 1632 KB Output is correct
11 Correct 27 ms 348 KB Output is correct
12 Correct 1266 ms 22884 KB Output is correct
13 Correct 1419 ms 23304 KB Output is correct
14 Correct 1534 ms 22112 KB Output is correct
15 Correct 1243 ms 21692 KB Output is correct
16 Correct 391 ms 592 KB Output is correct
17 Correct 988 ms 19236 KB Output is correct
18 Correct 981 ms 19912 KB Output is correct
19 Correct 1022 ms 19408 KB Output is correct
20 Correct 1002 ms 19412 KB Output is correct
21 Correct 1049 ms 19752 KB Output is correct
22 Correct 403 ms 484 KB Output is correct