QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#709641 | #8234. Period of a String | carott | WA | 372ms | 13952kb | C++20 | 5.7kb | 2024-11-04 16:00:24 | 2024-11-04 16:00:26 |
Judging History
answer
//Created by carottx on 2024-11-04.
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
namespace IO {
const int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc() \
(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
? EOF \
: *p1++)
int rd() {
int x = 0, f = 1;
char c = gc();
while (!isdigit(c)) {
if (c == '-') f = -1;
c = gc();
}
while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
return x * f;
}
char pbuf[1 << 20], *pp = pbuf;
void push(const char &c) {
if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
*pp++ = c;
}
void clear(){
fwrite(pbuf, 1, strlen(pbuf), stdout);
pp = pbuf;
}
void write(int x) {
static int sta[35];
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
}
} // namespace IO
const int maxn=100005;
const int INF=1e9+7;
// using namespace MYDEBUG;
int n;
string s[maxn];
string ans[maxn];
int len[maxn];
struct Restriction{
int len;
int cnt[26];
void clear(){len=0;memset(cnt, 0, sizeof(cnt));}
Restriction operator+(char c){
Restriction nr;
memcpy(nr.cnt, cnt, sizeof(cnt));
nr.cnt[c-'a']++;
nr.len = len+1;
return nr;
}
Restriction operator-(Restriction other){
Restriction nr;
for(int i=0; i<26; ++i) nr.cnt[i] = cnt[i] - other.cnt[i];
nr.len = len - other.len;
return nr;
}
Restriction operator*(int x){
Restriction nr;
nr.len = len*x;
for(int i=0; i<26; ++i) nr.cnt[i] = x*cnt[i];
return nr;
}
bool operator<(const Restriction& other)const{
return len < other.len;
}
bool check(){
for(int i=0;i<26;++i){
if(cnt[i] < 0) return false;
}
return true;
}
};
Restriction r[maxn];
void solve(){
// cerr<<"!!!!!!!!!!!!!!!!!!!!!!!"<<endl;
cin>>n;
// n=147;
for(int i=0; i<n; ++i) r[i].clear();
for(int i=0; i<n; ++i) {
cin>>s[i];
// s[i] = "";
// for(int j=0; j<5000; ++j) s[i] += 'a';
}
for(int i=0; i<n; ++i) {
len[i] = s[i].length();
Restriction& tmp = r[i];
tmp = tmp + s[i][0];
for(int j=1; j<len[i]; ++j){
tmp = tmp + s[i][j];
}
}
int LenOfFirst = len[0];
set<pii> S;
S.insert(pii(-1,0));
vector<Restriction> r0;
for(int i=1; i<n; ++i){
int NowLen = len[i];
auto tmp = r[i];
while(NowLen != 0){
auto it = upper_bound(S.begin(), S.end(), pii(NowLen,1e9));
it--;
int ModLen = it->first;
int id = it->second;
if(ModLen!=-1) {
tmp = tmp - r[id] * (NowLen/ModLen);
if(!tmp.check()) {
IO::push('N');
IO::push('O');
IO::push('\n');
return;
}
NowLen %= ModLen;
}
else {
tmp = tmp - r[id] * (NowLen/LenOfFirst);
NowLen %= LenOfFirst ;
break;
}
}
if(NowLen){
int mul = (len[i]-NowLen)/LenOfFirst;
r0.push_back(tmp);
}
S.insert(pii(len[i],i));
}
sort(r0.begin(),r0.end());
r0.push_back(r[0]);
Restriction now;
now.clear();
bool flag = false;
string& new0 = ans[0];
new0 = "";
for(auto& rr: r0){
Restriction tmp = rr-now;
for(int i=0; i<26; ++i)
{
if(tmp.cnt[i] < 0){
flag = true;
break;
}
else if(tmp.cnt[i] > 0){
for(int k=0; k<tmp.cnt[i]; ++k) new0 += i+'a';
}
}
now = rr;
}
for(int i=1; i<n && !flag; ++i){
int mul = len[i]/len[i-1];
auto delta = r[i] - r[i-1] * mul;
if(!delta.check()) {flag=true;if(n>=50)cout<<"FUCK"<<endl;break;}
ans[i] = "";
for(int j=0; j<mul; ++j) ans[i] += ans[i-1];
for(int j=0; j<delta.len; ++j){
if(delta.cnt[ans[i-1][j]-'a']<=0) {flag=true;if(n>=50)cout<<"FUCK2"<<endl;break;}
delta.cnt[ans[i-1][j]-'a'] --;
ans[i] += ans[i-1][j];
}
}
if(flag) {
IO::push('N');
IO::push('O');
IO::push('\n');
return;
}
IO::push('Y');
IO::push('E');
IO::push('S');
IO::push('\n');
for(int i=0;i<n;++i){
for(int j=0; j<ans[i].length(); ++j) IO::push(ans[i][j]);
IO::push('\n');
}
}
int main(){
// freopen("output.txt","w",stderr);
// freopen("test.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--) solve();
IO::clear();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11800kb
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: 0
Accepted
time: 0ms
memory: 11688kb
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
result:
ok ok (5 test cases)
Test #3:
score: -100
Wrong Answer
time: 372ms
memory: 13952kb
input:
100 147 ababbbaaaaaababbbbbaabaabbbbaaaababbbbababaabbbbaaabbabaaaaaabbbbaabbaaaaaababbbaabbabbaaabbbaabbbabaabbbbaabaabbaa aaaaabbbbababababbbaaaaaabaaaaabbaabaabaaababbabbabbabbaabbaaabbaabbaabaababaaabbababbbbbaabaaaaabbbbaabbbbbbaaabbbbabaababbbbb ababbabaababbbbaabbbbaaabbabaabbaaaababbbabbaaab...
output:
NO NO NO NO NO NO YES bbaaaaabbbbbbbbbbb bb bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb bb bbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbbbbbbbbbbbbbbb bbbb bbbbbbbbbbbb bbbbbb bbbbb bbbbbbbbbb bbb bbb b bbbbbbbbbbbbbbbbb bbbb bbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbbbb b bbb bbbbbbbbbbbbbbbbb bbbbbb bbbbb bbbbbbbbbbbbbbb...
result:
wrong answer Jury has the answer but participant has not (test case 2)