QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#714554 | #8234. Period of a String | Rhine | RE | 0ms | 3604kb | C++20 | 5.1kb | 2024-11-06 00:04:11 | 2024-11-06 00:04:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct Node : public std::array<int, 26> {
using std::array<int, 26>::array;
Node operator+(const Node &y) const {
Node ans;
for(int i = 0; i < 26; i++) {
ans[i] = (*this)[i] + y[i];
}
return ans;
}
Node operator-(const Node &y) const {
Node ans;
for(int i = 0; i < 26; i++) {
ans[i] = (*this)[i] - y[i];
}
return ans;
}
Node operator*(const int x) const {
Node ans = *this;
for(int i = 0; i < 26; i++) {
ans[i] *= x;
}
return ans;
}
bool isEmpty() const {
for(int i = 0; i < 26; i++) {
if((*this)[i] != 0) {
return false;
}
}
return true;
}
bool operator!=(const Node &y) const {
if(this->isEmpty() || y.isEmpty()) {
return false;
} else {
return !((*this) == y);
}
}
bool operator>(const Node &y) {
for(int i = 0; i < 26; i++) {
if((*this)[i] < y[i]) {
return false;
}
}
return true;
}
bool operator<<(const Node &y) {
if((*this) != y) {
return false;
}
if(!y.isEmpty()) {
(*this) = y;
}
return true;
}
};
void assign_string(string &s, int l, int r, Node node) {
int p = 0;
for(int i = l; i <= r; i++) {
while(p < 26 && node[p] == 0) {
p++;
}
s[i] = (char)('a' + p);
node[p]--;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) {
int n;
cin >> n;
vector<string> s(n);
vector<int> sz(n);
vector<Node> cnt(n);
vector<vector<Node>> cst(n);
for(int i = 0; i < n; i++) {
cin >> s[i];
for(auto ch : s[i]) {
cnt[i][ch - 'a']++;
}
sz[i] = s[i].size();
cst[i].resize(s[i].size());
}
cst[0].back() = cnt[0];
bool fl = true;
for(int i = 1; i < n; i++) {
for(int j = 0; j < s[i].size(); j++) {
if(j < sz[i - 1]) {
cst[i][j] = cst[i - 1][j];
} else if(!cst[i][j - sz[i - 1]].isEmpty()) {
cst[i][j] = cst[i][j - sz[i - 1]] + cnt[i - 1];
}
}
if(cst[i].back() != cnt[i]) {
fl = false;
break;
}
cst[i].back() = cnt[i];
if(sz[i] % sz[i - 1] != 0 && sz[i] > sz[i - 1]) {
auto t = cnt[i] - cnt[i - 1] * (sz[i] / sz[i - 1]);
if(t != cst[i][(sz[i] - 1) % sz[i - 1]]) {
fl = false;
break;
} else {
cst[i][(sz[i] - 1) % sz[i - 1]] = t;
}
}
}
for(int i = n - 1; i > 0 && fl; i--) {
for(int j = 0; j < sz[i] && fl; j++) {
if(!cst[i][j].isEmpty()) {
fl = (fl && (cst[i - 1][j % sz[i - 1]] << (cst[i][j] - cnt[i - 1] * (j / sz[i - 1]))));
}
}
}
for(int i = 1; i < n && fl; i++) {
for(int j = 0; j < s[i].size(); j++) {
if(j < sz[i - 1]) {
if(cst[i - 1][j] != cst[i][j]) {
fl = false;
break;
} else if(!cst[i - 1][j].isEmpty()) {
cst[i][j] = cst[i - 1][j];
}
} else if(!cst[i][j - sz[i - 1]].isEmpty()) {
auto t = cst[i][j - sz[i - 1]] + cnt[i - 1];
if(t != cst[i][j]) {
fl = false;
break;
} else if(!t.isEmpty()) {
cst[i][j] = t;
}
}
}
}
vector<string> ans = s;
for(int i = 0; i < n; i++){
int last = s[i].size() - 1;
for(int j = s[i].size() - 2; j >= 0; j--) {
if(!cst[i][j].isEmpty()) {
if(cst[i][last] > cst[i][j]) {
assign_string(ans[i], j + 1, last, cst[i][last] - cst[i][j]);
last = j;
} else {
fl = false;
break;
}
}
}
assign_string(ans[i], 0, last, cst[i][last]);
}
// for(int i = 1; i < n && fl; i++) {
// for(int j = 0; j < sz[i]; j++) {
// ans[i][j] = ans[i - 1][j % sz[i - 1]];
// }
// }
if(fl) {
cout << "YES" << endl;
for(auto & str : ans) {
cout << str << endl;
}
} else {
cout << "NO" << endl;
}
}
}
//
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
4 2 abc abcd 4 bbcaa cabb acabbbb a 3 ab aab bbaaaaab 3 ab aab bbaaaaaa
output:
NO YES abbca abbc abbcabb a YES ab aba abaabaab NO
result:
ok ok (4 test cases)
Test #2:
score: -100
Runtime Error
input:
5 1 ccecddbdbbcbbaded 3 cd d d 1 dcedec 2 dcec cce 8 a e a c cc cccccccc c b
output:
YES abbbbbccccdddddee YES dc d d YES ccddee YES cced cce NO