답안 #731362

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
731362 2023-04-27T11:04:49 Z eneskav Političari (COCI20_politicari) C++17
10 / 70
16 ms 2004 KB
// No bits/stdc++.h because clang

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <cassert>
#include <random>
#include <type_traits>
#include <list>
#include <tuple>
#include <climits>

// I don't know how any of these work, but its nice to have them
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline,unsafe-math-optimizations")
#pragma GCC target("avx,avx2,fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template <typename T>
void debug(T &x, std::string name = "")
{
    if (name == "")
        std::cerr << ":= " << x << "\n";
    else
        std::cerr << name << " = " << x << "\n";
}
template <typename T>
void debugArr(T &arr, int n = -1, std::string name = "")
{
    if (n == -1)
        n = sizeof(arr) / sizeof(arr[0]);
    if (name == "")
        std::cerr << ":= ";
    else
        std::cerr << name << " = ";
    std::cerr << "[";
    for (int i = 0; i < n; i++)
        std::cerr << arr[i] << ","[i == n - 1];
    std::cerr << "]"
              << "\n";
}
template <typename T>
void debugArr(std::vector<T> &arr, int n = -1, std::string name = "")
{
    if (n == -1)
        n = arr.size();
    if (name == "")
        std::cerr << ":= ";
    else
        std::cerr << name << " = ";
    std::cerr << "[";
    for (int i = 0; i < n; i++)
        std::cerr << arr[i] << ","[i == n - 1];
    std::cerr << "]"
              << "\n";
}
using namespace std;
/******************* Uncomment this for long long (TLE) *******************/
// #define int long long
#define vint vector<int>
#define pint pair<int, int>
#define mint map<int, int>
#define sint set<int>
#define msint multiset<int>
#define qint queue<int>
#define pqint priority_queue<int>
#define lint list<int>
#define stint stack<int>
#define gint greater<int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define guv   \
    int u, v; \
    cin >> u >> v
#define sz(x) (int)x.size()
#define cinarr(x, n)            \
    for (int i = 0; i < n; i++) \
    cin >> x[i]
#define coutarr(x, n)           \
    for (int i = 0; i < n; i++) \
        cout << x[i] << " ";    \
    cout << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define _reset(x, y) memset(x, y, sizeof(x))
#define _mid ((l + r) >> 1)
#define endl "\n"
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define FILEIO freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)

inline void swap(int &a, int &b)
{
    a ^= b;
    b ^= a;
    a ^= b;
}

inline int gcd(int a, int b)
{
    while (b)
    {
        a %= b;
        swap(a, b);
    }
    return a;
}

/*
 _____ ____  ____  ____    _     _     ____  _  __
/  __//  _ \/  _ \/  _ \  / \   / \ /\/   _\/ |/ /
| |  _| / \|| / \|| | \|  | |   | | |||  /  |   /
| |_//| \_/|| \_/|| |_/|  | |_/\| \_/||  \_ |   \
\____\____/\____/\____/  \____/\____/\____/\_|\_\
*/
inline void solve()
{

    int n, k;
    cin >> n >> k;
    int a[n + 1][n + 1];
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            cin >> a[i][j];
        }
    }
    if (k <= 2)
    {
        cout << k << endl;
        return;
    }
    bool vis[n + 1][n + 1]; // now, last
    _reset(vis, false);
    int last = 2;
    int now = a[2][1];
    vint v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(now);
    vis[now][last] = true;
    vis[2][1] = true;
    int len = 3;
    for (int i = 3; i <= k * 2; ++i)
    {
        int temp = now;
        now = a[now][last];
        last = temp;
        if (vis[now][last])
        {
            --len;
            break;
        }
        v.push_back(now);
        vis[now][last] = true;
        ++len;
        // cout << "i: " << i << " now: " << now << " last: " << last << endl;
    }
    // print v
    /* for (int i = 0; i < len; ++i)
    {
        cout << v[i] << " ";
    }
    cout << endl; */
    cout << v[(k - 1) % len] << endl;

    // My code is not working!!! Try these fixes:
    // 1. Check for overflow (uncommenct #define int long long)
    // 2. Check for array bounds
    // 3. Check for array indexes, 1-indexed or 0-indexed?
    // 4. Check for special cases (n=1?)
    // 5. Check for multiple test cases (remember to clear global variables)
    // 6. Check the limits of your data types maybe l <= r, maybe 0 <= n...

    // Getting TLE? Try these fixes:
    // 1. Delete the line: #define int long long
    // 2. Use array instead of vector

    // Getting WA? Good luck, you're on your own
}

signed main()
{
    int t = 1;
    FASTIO;
    /******************* Uncomment this if you want to read from input.txt ********************/


    /***************** Uncomment this if you want to test multiple test cases *****************/
    // cin >> t;

    for (int i = 1; i <= t; i++)
    {
        /**************** Uncomment this if you want to print the case number ****************/
        // cout << "Case " << i << ":" << endl;
        solve();
    }

    return '0' ^ '0';
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 596 KB Output isn't correct
3 Incorrect 2 ms 1108 KB Output isn't correct
4 Incorrect 3 ms 1352 KB Output isn't correct
5 Incorrect 3 ms 1492 KB Output isn't correct
6 Incorrect 3 ms 1492 KB Output isn't correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 2 ms 340 KB Output isn't correct
9 Incorrect 4 ms 724 KB Output isn't correct
10 Incorrect 13 ms 1764 KB Output isn't correct
11 Incorrect 16 ms 2004 KB Output isn't correct
12 Incorrect 15 ms 1940 KB Output isn't correct
13 Incorrect 1 ms 212 KB Output isn't correct
14 Incorrect 2 ms 440 KB Output isn't correct