#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define tobit(n) bitset<128>(n)
#define all(v) (v).begin(), (v).end()
#define rtt(v) rotate(vec.begin(), vec.begin() + k, vec.end()); //move k elements back
int dx[] = {1,0,-1,0,1,1,-1,-1}; int dy[] = {0,1,0,-1,1,-1,1,-1};
const int MOD = 1000000007;
const int MAXN = 2005;
int binpownm(int n, int m){
if(m <= 1) return n;
if(m % 2 == 0){
int t = binpownm(n, m / 2); return t * t;
} else return binpownm(n, m - 1) * n;
}
string tobin(int n){
if(n == numeric_limits<int>::min()) return "-1" + string(numeric_limits<int>::digits, '0');
string res;
res.reserve(numeric_limits<int>::digits + 1);
bool cur = (n < 0);
if(cur) n = -n;
do { res += char('0' + n % 2); n = n / 2; } while (n > 0);
if(cur) res += '-';
return string(res.crbegin(), res.crend());
}
void merge(vector<int>& v, int l, int m, int r){
vector<int> result;
int i = l, j = m + 1;
while(i <= m && j <= r){
if(v[i] <= v[j]) result.emplace_back(v[i]), i++;
else result.emplace_back(v[j]), j++;
} while(i <= m){
result.emplace_back(v[i]); i++;
} while(j <= r){
result.emplace_back(v[j]); j++;
} for(int i = l; i <= r; i++) v[i] = result[i - l];
}
void mergeSORT(vector<int>& v, int l, int r){
if(l < r){
int m = (l + r) / 2;
mergeSORT(v, l, m);
mergeSORT(v, m + 1, r);
merge(v, l, m, r);
}
}
// Алгоритм Манакера || "Короче строка s и мы хотим найти в ней все подпалиндромы" //
vector<int> manacher_odd(string s){ //для нечетных размеров палиндромов
vector<int> v(s.size(), 1);
int l = 0, r = 0;
for(int i = 1; i < s.size(); i++){
if(i < r) v[i] = min(r - i + 1, v[l + r - i]);
while(i - v[i] >= 0 && i + v[i] < s.size() && s[i - v[i]] == s[i + v[i]]) v[i]++;
if(i + v[i] - 1 > r) l = i - v[i] + 1, r = i + v[i] - 1;
} return v;
}
// Алгоритм Манакера || "Короче строка s и мы хотим найти в ней все подпалиндромы" //
vector<int> manacher_even(string s){ //для четного размеров палиндромов
vector<int> v(s.size(), 0);
int l = -1, r = -1;
for(int i = 0; i < s.size() - 1; i++){
if(i < r) v[i] = min(r - i, v[l + r - i - 1]);
while (i - v[i] >= 0 && i + v[i] + 1 < s.size() && s[i - v[i]] == s[i + v[i] + 1]) v[i]++;
if(i + v[i] > r) l = i - v[i] + 1, r = i + v[i];
} return v;
}
// PRIMERNO kak pref function no on ishet maksimalnye stroki //
vector<int> z_func(string s){
vector<int> z(s.size());
z[0] = 0;
int l = 0, r = 0;
for(int i = 1; i < s.size(); i++){
if(i <= r){
z[i] = min(z[i - l], r - i + 1);
}
while(i + z[i] < s.size() && s[z[i]] == s[i + z[i]]){
z[i] += 1;
}
if(i + z[i] - 1 > r){
l = i;
r = i + z[i] - 1;
}
} return z;
}
int BIN(vector<int> v, int l, int r, int x){
if(r >= l){
int m = l + (r - l) / 2;
if(v[m] == x) return m;
if(v[m] > x) return BIN(v, l, m - 1, x);
return BIN(v, m + 1, r, x);
} return -1;
}
// PREFIX FUNC p[i] = kolichestvo kakoihto sufix p[i] ravnyy prefu //
vector<int> p_func(string s){
vector<int> p(s.size(), 0);
for(int i = 1; i < s.size(); i++){
int cur = p[i - 1];
while(s[i] != s[cur] && cur > 0) cur = p[cur - 1];
if(s[i] == s[cur]) p[i] = cur + 1;
} return p;
}
// check to find element in 2D array //
vector<int> FIND2D(vector<vector<int>>& v, int k){
for(int i = 0; i < v.size(); i++){
vector<int> cur;
for(int j = 0; j < v[i].size(); j++){
cur.emplace_back(v[i][j]);
}
int res = BIN(cur, 0, cur.size() - 1, k);
vector<int> qwe;
qwe.emplace_back(i);
qwe.emplace_back(res);
if(res != -1) return qwe;
}
vector<int> qwe = {-1};
return qwe;
}
int lis(vector<int>& arr) {
int n = arr.size();
vector<int> lis(n, 1);
for(int i = 1; i < n; i++){
for(int prev = 0; prev < i; prev++){
if(arr[i] > arr[prev] && lis[i] < lis[prev] + 1){
lis[i] = lis[prev] + 1;
}
}
} return *max_element(lis.begin(), lis.end());
}
vector<vector<int>> build_prefix_sums_2d(const vector<vector<int>>& a){
int n = a.size();
int m = a[0].size();
vector<vector<int>> prefix_sum(n + 1 , vector<int>(m + 1, 0));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
prefix_sum [i + 1][ j + 1] = prefix_sum[i][j + 1] + prefix_sum[i + 1][j] - prefix_sum[i][j] + a[i][j];
}
} return prefix_sum;
}
int findGCD(vector<int> arr, int n){
int result = arr[0];
for(int i = 1; i < n; i++) result = __gcd(arr[i], result);
return result;
}
bool isPrime(int n){
if(n <= 1) return false;
if(n <= 3) return true;
if(n % 2 == 0 || n % 3 == 0) return false;
for(int i = 5; i * i <= n; i += 6){
if(n % i == 0 || n % (i + 2) == 0) return false;
} return true;
}
vector<vector<int>> g; vector<int> vis;
void dfs(int c){
vis[c] = true;
for(auto to : g[c]){
if(vis[to]) continue;
dfs(to);
}
}
int n, p[MAXN];
vector<int> ans;
void FUNC(int x){
x = n - x;
rotate(p, p + n - x, p + n);
reverse(p, p + x);
ans.push_back(x);
}
void solve(){
int cur = (n / 2) * 2;
bool rev = 0;
while(cur >= 2){
int x, y;
if(cur == n) x = 0, y = 1;
else{
x = p[cur]; y = p[n - 1];
if(!rev) x--, y++;
else x++, y--;
} x = (x + n) % n; y = (y + n) % n;
int px = find(p, p + n, x) - p;
FUNC(px + 1); FUNC(0); FUNC(cur);
int py = find(p, p + n, y) - p; FUNC(py);
int pxx = find(p, p + n, x) - p; FUNC(pxx + 1);
rev ^= 1; cur -= 2;
} if(n > 1){
int pos = find(p, p + n, 0) - p;
if(p[(pos + 1) % n] == n - 1) FUNC(0);
pos = find(p, p + n, 0) - p;
FUNC(pos); FUNC(n - pos); FUNC(0);
}
}
signed main(){
string s, t; int m;
cin >> n >> m >> s >> t;
vector<int> r1(n), r2(n);
iota(r1.begin(), r1.end(), 0); iota(r2.begin(), r2.end(), 0);
sort(r1.begin(), r1.end(), [&](int x, int y){
return s[x] < s[y];
}); //cout << s << endl;
sort(r2.begin(), r2.end(), [&](int x, int y){
return t[x] < t[y];
}); //cout << t << endl;
// for(auto to : r1) cout << to << " "; cout << endl;
// for(auto to : r2) cout << to << " "; cout << endl;
for(int i = 0; i < n; i++){
if(s[r1[i]] != t[r2[i]]){
puts("-1");
return 0;
}
p[r1[i]] = r2[i];
} for(auto to : p) cout << to << " ";
solve();
cout << ans.size() << endl;
for(auto &i : ans) printf("%d ", i);
}
const int fastIO = [](){
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
return 0;
}();
Compilation message
A.cpp: In function 'std::vector<long long int> manacher_odd(std::string)':
A.cpp:52: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]
52 | for(int i = 1; i < s.size(); i++){
| ~~^~~~~~~~~~
A.cpp:54:41: 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]
54 | while(i - v[i] >= 0 && i + v[i] < s.size() && s[i - v[i]] == s[i + v[i]]) v[i]++;
| ~~~~~~~~~^~~~~~~~~~
A.cpp: In function 'std::vector<long long int> manacher_even(std::string)':
A.cpp:62: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]
62 | for(int i = 0; i < s.size() - 1; i++){
| ~~^~~~~~~~~~~~~~
A.cpp:64:46: 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]
64 | while (i - v[i] >= 0 && i + v[i] + 1 < s.size() && s[i - v[i]] == s[i + v[i] + 1]) v[i]++;
| ~~~~~~~~~~~~~^~~~~~~~~~
A.cpp: In function 'std::vector<long long int> z_func(std::string)':
A.cpp:73: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]
73 | for(int i = 1; i < s.size(); i++){
| ~~^~~~~~~~~~
A.cpp:77:24: 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]
77 | while(i + z[i] < s.size() && s[z[i]] == s[i + z[i]]){
| ~~~~~~~~~^~~~~~~~~~
A.cpp: In function 'std::vector<long long int> p_func(std::string)':
A.cpp:97: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]
97 | for(int i = 1; i < s.size(); i++){
| ~~^~~~~~~~~~
A.cpp: In function 'std::vector<long long int> FIND2D(std::vector<std::vector<long long int> >&, long long int)':
A.cpp:105:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
A.cpp:107:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int j = 0; j < v[i].size(); j++){
| ~~^~~~~~~~~~~~~
A.cpp: In function 'int main()':
A.cpp:214:33: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
214 | for(auto &i : ans) printf("%d ", i);
| ~^ ~
| | |
| int long long int
| %lld
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Extra information in the output file |
| 2 |
Halted |
0 ms |
0 KB |
- |
