Task: | String padding |
Sender: | Rasse |
Submission time: | 2024-11-04 22:19:03 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | WRONG ANSWER | 0.00 s | details |
#2 | WRONG ANSWER | 0.00 s | details |
#3 | WRONG ANSWER | 0.00 s | details |
#4 | WRONG ANSWER | 0.00 s | details |
#5 | WRONG ANSWER | 0.00 s | details |
#6 | WRONG ANSWER | 0.01 s | details |
#7 | WRONG ANSWER | 0.01 s | details |
#8 | WRONG ANSWER | 0.01 s | details |
#9 | WRONG ANSWER | 0.01 s | details |
#10 | WRONG ANSWER | 0.01 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | WRONG ANSWER | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
#14 | WRONG ANSWER | 0.01 s | details |
#15 | WRONG ANSWER | 0.01 s | details |
#16 | ACCEPTED | 0.00 s | details |
#17 | ACCEPTED | 0.00 s | details |
#18 | WRONG ANSWER | 0.01 s | details |
Compiler report
input/code.cpp: In function 'void solve()': input/code.cpp:32:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 32 | for (int i = 0; i < s.size(); i++) | ~~^~~~~~~~~~ input/code.cpp:39:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 39 | while (r < s.size() && s[l] == s[r]) | ~~^~~~~~~~~~ input/code.cpp:58:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 58 | while (r < s.size() && s[l] == s[r]) | ~~^~~~~~~~~~ input/code.cpp:68:25: warning: comparison of integer expressions of d...
Code
#include <iostream> #include <vector> #include <array> #include <string> #include <algorithm> #include <numeric> #include <unordered_map> #include <unordered_set> #include <set> #include <queue> #include <climits> #include <cmath> #include <functional> #include <type_traits> #include <bitset> #include <fstream> #define int long long using namespace std; int mod = 10e9+7; void solve() { int n; string s; cin >> n >> s; vector<int> zArr(s.size()); vector<int> res; int l = 0, r = 0; for (int i = 0; i < s.size(); i++) { if (i > r) { // Use naive r = i; l = 0; while (r < s.size() && s[l] == s[r]) { l++; r++; } r--; l = i; zArr[i] = r-i+1; } else { if (zArr[i-l] < r-i+1) { zArr[i] = zArr[i-l]; } else { l = r-i+1; r = r+1; while (r < s.size() && s[l] == s[r]) { l++; r++; } l = i; r--; zArr[i] = r-l+1; } } if (zArr[i] + i == s.size()) res.push_back(zArr[i]); } /* for (int i = res.size()-1; i >= 0; i--) { cout << res[i] << " "; } */ vector<int> mult(n); mult[0] = 1; for (int i = 1; i < mult.size(); i++) mult[i] = (mult[i-1] * 26) % mod; vector<int> dp(n); for (int i = 0; i < s.size(); i++) { dp[i] = 0; } dp[s.size()-1] = 1; for (int i = s.size(); i < dp.size(); i++) { dp[i] = mult[i-s.size()+1]; for (int j = 0; j < res.size(); j++) { dp[i] = (dp[i] - dp[i-s.size()+res[j]]) % mod; } for (int j = 0; j <= i-s.size(); j++) dp[i] = (dp[i] - dp[j]*mult[i-s.size()-j]) % mod; dp[i] = (dp[i] + mod) % mod; //cout << i << ": " << dp[i] << endl; } int result = 0; int multiple = 1; for (int i = n-1; i >= 0; i--) { result += dp[i] * multiple; multiple *= 26; multiple %= mod; result %= mod; } cout << result; } signed main() { //cin.tie(0); //ios_base::sync_with_stdio(false); int t = 1; //ifstream f("testcase.txt"); //cin.rdbuf(f.rdbuf()); //cin >> t; while (t--) { solve(); } }
Test details
Test 1
Verdict: WRONG ANSWER
input |
---|
100 YWANYWAZYWANYWA |
correct output |
---|
134837038 |
user output |
---|
3669728878 |
Test 2
Verdict: WRONG ANSWER
input |
---|
100 EDMXEDVNEDMXED |
correct output |
---|
642715950 |
user output |
---|
1836722421 |
Test 3
Verdict: WRONG ANSWER
input |
---|
100 SDARSDAWVSDARSDA |
correct output |
---|
748728234 |
user output |
---|
3918003778 |
Test 4
Verdict: WRONG ANSWER
input |
---|
100 HBDHBSHBDHB |
correct output |
---|
594110560 |
user output |
---|
9592054702 |
Test 5
Verdict: WRONG ANSWER
input |
---|
100 CUNXUYGNGNEROXVLASQB |
correct output |
---|
675706202 |
user output |
---|
9458098345 |
Test 6
Verdict: WRONG ANSWER
input |
---|
1000 LZAOLRKGLZAOLXLZAOLRKGLZAOLTLZ... |
correct output |
---|
318756627 |
user output |
---|
5414463549 |
Test 7
Verdict: WRONG ANSWER
input |
---|
1000 SUASJSUASSGDSUASJSUASGKSUASJSU... |
correct output |
---|
367950233 |
user output |
---|
5515189016 |
Test 8
Verdict: WRONG ANSWER
input |
---|
1000 NHYGNHEWNHYGNHFSNHYGNHEWNHYGNH... |
correct output |
---|
849646061 |
user output |
---|
4528629036 |
Test 9
Verdict: WRONG ANSWER
input |
---|
1000 ZOCUZOCGRFZOCUZOCOQZOCUZOCGRFZ... |
correct output |
---|
32142571 |
user output |
---|
4451802375 |
Test 10
Verdict: WRONG ANSWER
input |
---|
1000 LJZMKDTECKBXBTQQUMLGADBDNGWGPY... |
correct output |
---|
26128120 |
user output |
---|
5242115002 |
Test 11
Verdict: ACCEPTED
input |
---|
1 A |
correct output |
---|
1 |
user output |
---|
1 |
Test 12
Verdict: WRONG ANSWER
input |
---|
100 AVXETIDRHKPAKRBEAAVHLOPFACULSE... |
correct output |
---|
228794815 |
user output |
---|
1174258623 |
Test 13
Verdict: ACCEPTED
input |
---|
3 ABC |
correct output |
---|
1 |
user output |
---|
1 |
Test 14
Verdict: WRONG ANSWER
input |
---|
745 RRQOVUJRQBIMIQK |
correct output |
---|
504765084 |
user output |
---|
8986397972 |
Test 15
Verdict: WRONG ANSWER
input |
---|
666 ABCABCDABCABCX |
correct output |
---|
920654188 |
user output |
---|
6439897941 |
Test 16
Verdict: ACCEPTED
input |
---|
6 AA |
correct output |
---|
2212651 |
user output |
---|
2212651 |
Test 17
Verdict: ACCEPTED
input |
---|
1 B |
correct output |
---|
1 |
user output |
---|
1 |
Test 18
Verdict: WRONG ANSWER
input |
---|
1000 OMAKARAAA |
correct output |
---|
408042378 |
user output |
---|
3577270380 |