Submission #486744

#	Time	Username	Problem	Language	Result	Execution time	Memory
486744		davi_bart	Hop (COCI21_hop)	C++14	110 / 110	35 ms	6728 KiB

Main

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fi first
#define se second
#define ld long double
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int hop[1200][3];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> v(N);
    vector<vector<int> > ans(N);
    for (int &i : v) cin >> i;

    for (int i = N - 1; i >= 0; i--) {
        int k = 0;
        for (int j = i + 1; j < N; j++) {
            for (; k < 3; k++) {
                if (v[j] % v[i]) {
                    ans[j].pb(k);
                    break;
                }
                if (hop[j][k] < 3) {
                    ans[j].pb(k);
                    hop[i][k] = max(hop[i][k], hop[j][k] + 1);
                    break;
                }
                if (k == 2) {
                    k = 0;
                    ans[j].pb(rng() % 3);
                    break;
                }
            }
        }
    }
    // for (int j = 0; j < N; j++) {
    //     for (int k = 0; k < 3; k++) {
    //         cout << hop[j][k] << " ";
    //     }
    //     cout << endl;
    // }
    for (int i = 0; i < N; i++) {
        reverse(ans[i].begin(), ans[i].end());
        for (int x : ans[i]) {
            cout << x + 1 << " ";
        }
        cout << '\n';
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 100 / 100