oj.uz

Submission #845500

# Submission time Handle Problem Language Result Execution time Memory
845500 2023-09-06T13:54:01 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 24144 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));
}

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 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2128 KB Output is correct
2 Correct 80 ms 1872 KB Output is correct
3 Correct 78 ms 1872 KB Output is correct
4 Correct 31 ms 344 KB Output is correct
5 Correct 70 ms 1668 KB Output is correct
6 Correct 73 ms 1976 KB Output is correct
7 Correct 32 ms 344 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 83 ms 2128 KB Output is correct
6 Correct 80 ms 1872 KB Output is correct
7 Correct 78 ms 1872 KB Output is correct
8 Correct 31 ms 344 KB Output is correct
9 Correct 70 ms 1668 KB Output is correct
10 Correct 73 ms 1976 KB Output is correct
11 Correct 32 ms 344 KB Output is correct
12 Execution timed out 2017 ms 24144 KB Time limit exceeded
13 Halted 0 ms 0 KB -