QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#305232 | #7956. Walk Swapping | mshcherba | WA | 1ms | 3492kb | C++20 | 1.6kb | 2024-01-14 22:54:09 | 2024-01-14 22:54:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int INF = 1e9;
VI zFunction(const VI& s)
{
int n = SZ(s);
VI z(n);
int l = 0, r = 0;
FOR(i, 1, n)
{
z[i] = 0;
if (i <= r)
z[i] = min(r - i + 1, z[i - l]);
while (i + z[i] < n && s[i + z[i]] == s[z[i]])
z[i]++;
if (i + z[i] - 1 > r)
{
r = i + z[i] - 1;
l = i;
}
}
return z;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
int n;
cin >> n;
VI a(n), b(n);
for (int& x : a)
cin >> x;
for (int& x : b)
cin >> x;
VI c;
int ans = INF;
FOR(i, 0, n)
{
c.clear();
FOR(j, 0, n - 1)
c.PB(a[(i + j) % n]);
VI d1 = c, d2 = c;
reverse(ALL(d2));
d1.PB(0);
d1.insert(d1.end(), ALL(b));
d1.insert(d1.end(), ALL(b));
VI br = b;
reverse(ALL(br));
d2.PB(0);
d2.insert(d2.end(), ALL(br));
d2.insert(d2.end(), ALL(br));
VI z1 = zFunction(d1), z2 = zFunction(d2);
FOR(j, 0, n)
{
int x = z2[2 * n - j];
if (z1[n + j] + x >= n - 1 && b[(n + j - 1 - x) % n] == a[(i + n - 1) % n])
{
ans = min(ans, (n - 1 - j) % (n - 1) * (n - 1) + max(0, n - 1 - x));
}
}
b.PB(b[0]);
b.erase(b.begin());
}
cout << (ans == INF ? -1 : ans) << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3448kb
input:
4 4 3 2 1 3 4 2 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
6 2 1 1 2 2 1 1 2 2 2 1 1
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
6 4 1 3 6 2 5 6 2 1 3 4 5
output:
-1
result:
ok single line: '-1'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3456kb
input:
4 1 2 3 4 4 2 1 3
output:
1
result:
wrong answer 1st lines differ - expected: '2', found: '1'