oj.uz

Submission #848290

# Submission time Handle Problem Language Result Execution time Memory
848290 2023-09-12T02:36:47 Z fcmalkcin Političari (COCI20_politicari) C++17
70 / 70
 15 ms 4184 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb  push_back
#define eb  emplace_back
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"

const int maxn = 505;
const ll mod = 1e9 + 7;
const ll base = 1e18;

int n;
int mat[maxn][maxn], bio[maxn][maxn], guest[maxn * maxn];

ll k;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> mat[i][j];
            --mat[i][j];
        }
    }

    int prev = 0, curr = 1;
    guest[1] = 0;
    guest[2] = 1;
    bio[prev][curr] = 2;
    for (int i = 3; (ll)i <= k; ++i) {
        int nxt = mat[curr][prev];
        prev = curr;
        curr = nxt;
        if (bio[prev][curr] == 0) {
            bio[prev][curr] = i;
            guest[i] = curr;
            continue;
        }
        int j = bio[prev][curr];
        int cycle = i - j;
        int ret = j + ((k - j) % cycle);
        cout << guest[ret] + 1 << endl;
        return 0;
    }

    cout << guest[k] + 1 << endl;
    return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 3 ms 2648 KB Output is correct
3 Correct 8 ms 3572 KB Output is correct
4 Correct 11 ms 3672 KB Output is correct
5 Correct 12 ms 4184 KB Output is correct
6 Correct 15 ms 4184 KB Output is correct
7 Correct 1 ms 2512 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 3 ms 2904 KB Output is correct
10 Correct 10 ms 3676 KB Output is correct
11 Correct 13 ms 4184 KB Output is correct
12 Correct 13 ms 4184 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct