제출 #210021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
210021		apostoldaniel854	Političari (COCI20_politicari)	C++14	70 / 70	26 ms	2168 KiB

politicari

/*
https://oj.uz/problem/view/COCI20_politicari
*/


#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

const int N = 500;

int politician[1 + N * N + 4];
int nxt[1 + N][1 + N];
int used[1 + N][1 + N];


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

    ll k;
    int n;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> nxt[i][j];
    nxt[1][0] = 2;
    int start, blamed;
    blamed = 0;
    start = 1;
    int step = 0;
    while (used[start][blamed] == 0) {
        used[start][blamed] = ++step;
        politician[step] = start;
        int cur = nxt[start][blamed];
        blamed = start;
        start = cur;
    }
    if (k < used[start][blamed]) {
        cout << politician[k] << "\n";
    }
    else {
        k -= used[start][blamed];
        int period = step - used[start][blamed] + 1;
        cout << politician[used[start][blamed] + k % period] << "\n";
    }
    return 0;
}

• Subtask 1: 70 / 70