QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#211043 | #7337. Grasshoppers | gondozu | RE | 4ms | 6552kb | C++14 | 3.6kb | 2023-10-12 00:27:35 | 2023-10-12 00:27:36 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define Gondozu ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector <pair<int, int>>;
using vvi = vector <vector<int>>;
const int OO = 1e9 + 5;
const int N = 2e5 + 5, M = 100 + 2;
int go[M][M], n, m;
ll subm(ll a, ll b) {
a -= b;
if (a < 0) a += m;
return a;
}
ll addm(ll a, ll b) {
a += b;
if (a >= m) a -= m;
return a;
}
void pre(){
double half = m/2.0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
if(i == j || (m%2 == 0 && j == addm(i, half))){
go[i][j] = i;
continue;
}
if(subm(i,j) < subm(j,i)){
if(subm(i,j) < half - subm(i,j))
go[i][j] = subm(i, 2 * subm(i,j));
else
go[i][j] = addm(i, 2*(half - subm(i,j)));
} else {
if(subm(j,i) < half - subm(j,i))
go[i][j] = addm(i, 2 * subm(j,i));
else
go[i][j] = subm(i, 2 * (half - subm(j,i)));
}
}
}
}
void trans(vi &a){
vi b(n);
for (int i = 0; i < n; ++i) {
b[i] = go[a[i]][a[(i+1)%n]];
}
a = b;
}
const int P1 = 100003, P2 = 100019, MOD = 1e9 + 7;
int pw1[N], pw2[N], inv1[N], inv2[N];
int mul(int a, int b) {
a = ((a % MOD) + MOD) % MOD;
b = ((b % MOD) + MOD) % MOD;
return (a * 1LL * b) % MOD;
}
int add(int a, int b) {
a = ((a % MOD) + MOD) % MOD;
b = ((b % MOD) + MOD) % MOD;
return (a + b) % MOD;
}
int fastPower(int base, int power) {
if (!power) return 1;
int ret = fastPower(base, power >> 1);
ret = mul(ret, ret);
if (power % 2) ret = mul(ret, base);
return ret;
}
void preprocess() {
pw1[0] = inv1[0] = pw2[0] = inv2[0] = 1;
int mulInv1 = fastPower(P1, MOD - 2);
int mulInv2 = fastPower(P2, MOD - 2);
for (int i = 1; i < N; i++) {
pw1[i] = mul(pw1[i - 1], P1);
pw2[i] = mul(pw2[i - 1], P2);
inv1[i] = mul(inv1[i - 1], mulInv1);
inv2[i] = mul(inv2[i - 1], mulInv2);
}
}
struct Hash {
vector <pair<int, int>> prefixHash;
Hash() {}
Hash(int n, const vi& a) {
prefixHash = vector < pair < int, int >> (n, {0, 0});
for (int i = 0; i < n; i++) {
prefixHash[i].F = mul(a[i], pw1[i]);
prefixHash[i].S = mul(a[i], pw2[i]);
if (i)
prefixHash[i] = {add(prefixHash[i].F, prefixHash[i - 1].F), add(prefixHash[i].S, prefixHash[i - 1].S)};
}
}
pair<int, int> getHashVal() {
return prefixHash.back();
}
};
void TC()
{
int t;
cin >> n >> m >> t;
pre();
vi a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
--a[i];
}
vi b = a;
map<pi, int> idx;
for (int i = 0; i < 100000; ++i) {
Hash h(n, b);
if(idx.count(h.getHashVal())){
t -= idx[h.getHashVal()];
a = b;
t %= i-idx[h.getHashVal()];
break;
}
idx[h.getHashVal()] = i;
trans(b);
}
assert(t < 100000);
while (t--){
trans(a);
}
for(int i: a) cout << i+1 << ' ';
}
int32_t main() {
Gondozu
int t = 1;
cin >> t;
preprocess();
while (t--) {
TC();
cout << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 6552kb
input:
2 3 5 1 1 1 2 3 5 4 1 1 2
output:
1 3 5 5 4 5
result:
ok 6 numbers
Test #2:
score: -100
Runtime Error
input:
92 3 5 5 4 2 3 3 5 5 3 1 5 3 5 5 4 3 5 3 5 5 3 3 2 3 5 5 1 3 3 3 5 5 2 3 3 3 5 5 3 3 2 3 5 5 4 2 5 3 5 5 1 2 4 3 5 5 4 5 1 3 5 5 4 1 4 3 5 5 1 1 2 3 5 5 1 1 4 3 5 5 1 1 4 3 5 5 5 2 4 3 5 5 5 5 1 3 5 5 2 5 5 3 5 5 3 2 5 3 5 5 1 2 3 3 5 5 1 1 1 3 5 5 4 3 1 3 5 5 1 3 4 3 5 5 1 5 1 3 5 5 1 4 4 3 5 5 5 2...