답안 #849040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
849040	2023-09-14T01:45:28 Z	vjudge1	Političari (COCI20_politicari)	C++17	70 / 70	16 ms	2912 KB

politicari

#include<bits/stdc++.h>
#define ii pair<int, int>
#define ll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
//#define ORDS
using namespace std;

#ifdef ORDS
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    using namespace __gnu_pbds;
    #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#endif

const int mod[2] = {1000000007, 998244353};
const int N = 503;
const string NAME = "";
const int lim = 2147483647;
//const long long lim = 9223372036854775807;
const double pi = acos(-1);
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int n, a[N][N];
long long k;
bool visited[N][N], v2[N][N];
vector<int> v;

#ifdef i128
ostream & operator << (ostream &out, const __int128 &x){
    __int128 i = x;
    vector<int> digits;
    while(i > 0){
        digits.pb(i % 10);
        i /= 10;
    }
    reverse(digits.begin(), digits.end());
    for(auto x : digits)
        out << x;
    return out;
}
#endif

void inp(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> a[i][j];
        }
    }
}

void solve(){
    if(k < 3){
        cout << k;
        return;
    }
    int i = 2, j = 1;
    long long x = 2;
    while(!visited[i][j]){
        visited[i][j] = true;
        ++x;
        int tmp = a[i][j];
        if(x == k){
            cout << a[i][j];
            return;
        }
        j = i;
        i = tmp;
    }
    while(!v2[i][j]){
        v2[i][j] = true;
        ++x;
        int tmp = a[i][j];
        v.pb(tmp);
        if(x == k){
            cout << a[i][j];
            return;
        }
        j = i;
        i = tmp;
    }
    k -= x;
    cout << v[(k - 1) % v.size()];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifdef TimeCalculation
        auto starttime = chrono::high_resolution_clock::now();
    #endif

    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }

    inp();
    solve();

    #ifdef TimeCalculation
        auto endtime = chrono::high_resolution_clock::now();
        auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count();
        cout << "\n=====" << "\nTime elapsed: " << duration << " ms\n";
    #endif
}

Compilation message

politicari.cpp: In function 'int main()':
politicari.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
politicari.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	3 ms	1112 KB	Output is correct
3	Correct	8 ms	2136 KB	Output is correct
4	Correct	11 ms	2392 KB	Output is correct
5	Correct	16 ms	2912 KB	Output is correct
6	Correct	14 ms	2648 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	856 KB	Output is correct
9	Correct	4 ms	1112 KB	Output is correct
10	Correct	11 ms	2392 KB	Output is correct
11	Correct	13 ms	2648 KB	Output is correct
12	Correct	12 ms	2648 KB	Output is correct
13	Correct	1 ms	600 KB	Output is correct
14	Correct	2 ms	856 KB	Output is correct