oj.uz

Submission #492746

# Submission time Handle Problem Language Result Execution time Memory
492746 2021-12-08T17:02:28 Z LittleCube Chess Rush (CEOI20_chessrush) C++14
28 / 100
 2000 ms 23948 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, R, C, c1, c2;
char c;

constexpr int P = 1e9 + 7;

#ifdef EVAL
#include "arithmetics.h"
#else
int Add(int a, int b)
{
    int ret = a % P;
    ret = (ret < 0 ? P + ret : ret) + (b % P);
    return (ret >= 0 ? ret % P : ret + P);
}
int Sub(int a, int b)
{
    int ret = a % P;
    ret = (ret < 0 ? P + ret : ret) - (b % P);
    return (ret >= 0 ? ret % P : ret + P);
}
int Mul(int a, int b)
{
    int ret = (1ll * (a % P) * (b % P)) % P;
    return (ret < 0 ? P + ret : ret);
}
int modpow(int base, int exp, int modulus = P)
{
    base %= modulus;
    int result = 1;
    while (exp > 0)
    {
        if (exp & 1)
            result = (1ll * result * base) % modulus;
        base = (1ll * base * base) % modulus;
        exp >>= 1;
    }
    return result;
}
int modinv(int a, int modulus = P)
{
    return modpow(a, modulus - 2);
}
int Div(int a, int b)
{
    int ret = b % P;
    ret = (1ll * (a % P) * modinv(ret < 0 ? P + ret : ret)) % P;
    return (ret < 0 ? P + ret : ret);
}
#endif

#define matrix vector<vector<int>>

matrix mul(matrix m1, matrix m2, int size)
{
    matrix m(size, vector<int>(size, 0));

    for (int i = 0; i < size; i++)
        for (int k = 0; k < size; k++)
            for (int j = 0; j < size; j++)
                m[i][j] = Add(m[i][j], Mul(m1[i][k], m2[k][j]));
    return m;
}

matrix fastpow(matrix base, ll p, int size)
{
    matrix a(size, vector<int>(size, 0));
    for (int i = 0; i < size; i++)
        a[i][i] = 1;
    while (p > 0)
    {
        if (p & 1)
            a = mul(a, base, size);
        p >>= 1;
        base = mul(base, base, size);
    }
    return a;
}

signed main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> R >> C >> N;
    matrix m(C, vector<int>(C, 0)), res;
    for (int i = 0; i < C; i++)
        for (int j = 0; j < C; j++)
            if (abs(i - j) <= 1)
                m[i][j] = 1;
    res = fastpow(m, R - 1, C);
    for (int i = 1; i <= N; i++)
    {
        cin >> c >> c1 >> c2;
        if(c == 'K')
            cout << R - 1 << " " << res[c1 - 1][c2 - 1] << '\n';
        else
            return 0;
    }
}

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 127 ms 460 KB Output is correct
3 Correct 106 ms 504 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 127 ms 460 KB Output is correct
3 Correct 106 ms 504 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 7 ms 332 KB Output is correct
7 Correct 78 ms 512 KB Output is correct
8 Correct 124 ms 576 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 127 ms 460 KB Output is correct
3 Correct 106 ms 504 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 7 ms 332 KB Output is correct
7 Correct 78 ms 512 KB Output is correct
8 Correct 124 ms 576 KB Output is correct
9 Correct 12 ms 332 KB Output is correct
10 Correct 20 ms 332 KB Output is correct
11 Correct 643 ms 692 KB Output is correct
12 Correct 562 ms 556 KB Output is correct
13 Correct 14 ms 340 KB Output is correct
14 Correct 1 ms 204 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 127 ms 460 KB Output is correct
3 Correct 106 ms 504 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 7 ms 332 KB Output is correct
7 Correct 78 ms 512 KB Output is correct
8 Correct 124 ms 576 KB Output is correct
9 Correct 12 ms 332 KB Output is correct
10 Correct 20 ms 332 KB Output is correct
11 Correct 643 ms 692 KB Output is correct
12 Correct 562 ms 556 KB Output is correct
13 Correct 14 ms 340 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 16 ms 352 KB Output is correct
16 Correct 17 ms 332 KB Output is correct
17 Execution timed out 2092 ms 23948 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -