oj.uz

Submission #486761

# Submission time Handle Problem Language Result Execution time Memory
486761 2021-11-12T18:03:24 Z davi_bart Hop (COCI21_hop) C++14
110 / 110
 48 ms 6616 KB 
// #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 << 1 << " ";
        }
        cout << '\n';
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:50:18: warning: unused variable 'x' [-Wunused-variable]
   50 |         for (int x : ans[i]) {
      |                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #2
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 41 ms 6616 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 37 ms 5748 KB Output is correct
12 Correct 42 ms 6528 KB Output is correct
13 Correct 37 ms 5928 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 37 ms 5928 KB Output is correct
16 Correct 39 ms 6036 KB Output is correct
17 Correct 39 ms 6084 KB Output is correct
18 Correct 48 ms 5916 KB Output is correct
19 Correct 38 ms 5956 KB Output is correct
20 Correct 37 ms 6052 KB Output is correct
21 Correct 37 ms 5932 KB Output is correct
22 Correct 37 ms 5912 KB Output is correct
23 Correct 46 ms 6596 KB Output is correct