QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211043#7337. GrasshoppersgondozuRE 4ms6552kbC++143.6kb2023-10-12 00:27:352023-10-12 00:27:36

Judging History

你现在查看的是最新测评结果

  • [2023-10-12 00:27:36]
  • 评测
  • 测评结果:RE
  • 用时:4ms
  • 内存:6552kb
  • [2023-10-12 00:27:35]
  • 提交

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;
}

详细

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...

output:


result: