Leimasin

input/code.cpp: In function 'void hsh(std::__cxx11::string)':
input/code.cpp:3:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, a, b) for (int i=a; i<(b); i++)
                                     ^
input/code.cpp:40:2: note: in expansion of macro 'FOR'
  FOR(i,1,x.size()) {
  ^~~
input/code.cpp: In function 'void makeCompact()':
input/code.cpp:3:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, a, b) for (int i=a; i<(b); i++)
                                     ^
input/code.cpp:100:2: note: in expansion of macro 'FOR'
  FOR(i,0,temp.size()-1) {
  ^~~

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define IO ios_base::sync_with_stdio(0); cin.tie(0)
#define ff first
#define ss second
#define pb push_back
#define INF 2147483647
#define LINF (1LL<<61LL)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define N 1003
ll A = 911382319, B = 972663749;
ll pA[N];
ll H[N], HASH[N];
ll pre[N], suff[N];
int n, m;
vector<int> pres, sufs, full;

// 0-indexed
ll rq(int a, int b) {
	if (a == 0) return H[b];
	ll h = (H[b]-H[a-1]*pA[b-a+1])%B;
	if (h<0) h+=B;
	return h;
}

ll ran(int a, int b) {
	if (a==0) return HASH[b];
	ll h = (HASH[b]-HASH[a-1]*pA[b-a+1])%B;
	if (h<0) h+=B;
	return h;
}

void hsh(string x) {
	HASH[0] = x[0];
	FOR(i,1,x.size()) {
		HASH[i] = (HASH[i-1]*A+x[i])%B;
	}
	FOR(l,0,m) {
		ll a = ran(0, l);
		ll b = ran(m-1-l,m-1);
		if (a < 0) a += B;
		if (b < 0) b += B;
		pre[l+1] = a;
		suff[l+1] = b;
	}
}

ll pure(const string& x) {
	ll h = 0;
	for (char c:x) h=(h*A+(ll)c)%B;
	return h;
}

string s, L;

set<pii> vr;
bool proc[N]; // processed
int pr = 0;

string w = "";
void paint(int p) {
	FOR(j,0,m) w[j+p] = L[j]; 
}

void solved() {
	int sz=pres.size()+full.size()+sufs.size();
	reverse(pres.begin(), pres.end());
	reverse(sufs.begin(), sufs.end());
	for (int pr : pres) paint(pr);
	for (int sf : sufs) paint(sf);
	for (int f : full) paint(f);
	
	cout<<sz<<"\n";
	for (int pr : pres) cout<<pr+1<<" ";
	for (int sf : sufs) cout<<sf+1<<" ";
	for (int f : full) cout<<f+1<<" ";
	exit(0);
}

void addProc(int x) {
	if (!proc[x]) pr++;
	proc[x] = true;
	if (pr == n) solved();
}

// inclusive
void process(int a, int b) {
	FOR(j,a,b+1) addProc(j);
}

void makeCompact() {
	set<pii> nw;
	vector<pii> temp;
	for (auto seg : vr) temp.pb(seg), nw.insert(seg);
	FOR(i,0,temp.size()-1) {
		if (temp[i].ss+1 == temp[i+1].ff) {
			// Concatenate
			vr.erase(temp[i]);
			vr.erase(temp[i+1]);
			vr.insert({temp[i].ff, temp[i+1].ss});
			cout<<"("<<temp[i].ff<<","<<temp[i].ss<<") & ";
			cout<<"("<<temp[i+1].ff<<","<<temp[i].ss<<") -> ";
			cout<<"("<<temp[i].ff<<","<<temp[i+1].ss<<")\n";
			temp[i+1] = {temp[i].ff, temp[i+1].ss};
		}
	}
	vr = nw;
}

int main() {
	IO;
	cin>>s; cin>>L;
	n = s.size();
	m = L.size();
	
	pA[0] = 1;
	H[0] = s[0];
	FOR(i,1,n+1) {
		H[i] = (H[i-1]*A+s[i])%B;
		pA[i] = pA[i-1]*A%B;
	}
	
	FOR(j,0,n) w+="?";
	
	hsh(L);
	ll label = pure(L);
	
	// Find all labels
	FOR(i,0,n-m+1) {
		if (proc[i]) continue;
		// Match for label
		if (rq(i,i+m-1) == label) {
			full.pb(i);
			vr.insert({i,i+m-1});
			process(i,i+m-1);
		}
	}
	
	while (vr.size()) {
		//makeCompact();
		// Try to spread a segment
		bool ext = false;
		auto seg = *vr.begin();
		int a = seg.ff, b = seg.ss;
		
		// Check for any prefix
		for (int l=1; l<=m; l++) {
			int lp = a-l;
			if (lp < 0) continue;
			if (proc[lp]) break;
			if (rq(lp,a-1) == pre[l]) {
				//cout<<"found prefix at "<<lp+1<<"\n";
				vr.erase(vr.begin());
				vr.insert({lp, b});
				pres.pb(lp);
				process(lp, a-1);
				ext = true;
				break;
			}
		}
		
		if (ext) continue;
		
		// Check for any suffix, as no prefix was found
		for (int l=1; l<=m; l++) {
			int rp = b+l;
			if (rp >= n) continue;
			if (proc[rp]) break;
			if (rq(b+1,rp) == suff[l]) {
				vr.erase(vr.begin());
				vr.insert({a,rp});
				sufs.pb(rp-m+1);
				process(b+1, rp);
				ext = true;
			}
		}
		
		if (ext) continue;
		
		vr.erase(vr.begin());
	}
	
	cout<<"-1\n";
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: WRONG ANSWER

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: WRONG ANSWER

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: WRONG ANSWER

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 3

Verdict: ACCEPTED

Test 30

Group: 3

Verdict: ACCEPTED

Test 31

Group: 3

Verdict: WRONG ANSWER

Test 32

Group: 3

Verdict: ACCEPTED

Test 33

Group: 3

Verdict: ACCEPTED

Test 34

Group: 3

Verdict: ACCEPTED

Test 35

Group: 3

Verdict: WRONG ANSWER

Test 36

Group: 3

Verdict: WRONG ANSWER

Test 37

Group: 3

Verdict: ACCEPTED

Test 38

Group: 3

Verdict: ACCEPTED

Test 39

Group: 3

Verdict: ACCEPTED

Test 40

Group: 3

Verdict: ACCEPTED

Test 41

Group: 3

Verdict: WRONG ANSWER

Test 42

Group: 3

Verdict: ACCEPTED