oj.uz

Submission #849040

# Submission time Handle Problem Language Result Execution time Memory
849040 2023-09-14T01:45:28 Z vjudge1 Političari (COCI20_politicari) C++17
70 / 70
 16 ms 2912 KB 
#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

# Verdict Execution time Memory 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