Submission #775088

#	Time	Username	Problem	Language	Result	Execution time	Memory
775088		vjudge1	Stone Arranging 2 (JOI23_ho_t1)	C++98	100 / 100	195 ms	13164 KiB

Main

// #pragma GCC target("abm")
// #pragma GCC optimize("03,unroll-loops")
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")
// #pragma GCC target("avx2")

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr)

#define put(a) cout << a << "\n"
#define put_2(a, b) cout << a << " " << b << "\n"
#define put_3(a, b, c) cout << a << " " << b << " " << c << "\n"
#define put_4(a, b, c, x) cout << a << " " << b << " " << c << " " << x << "\n"
#define put_5(a, b, c, x, y) cout << a << " " << b << " " << c << " " << x << " " << y << "\n";
#define put_6(a, b, c, x, y, z) cout << a << " " << b << " " << c << " " << x << " " << y << " " << z << "\n";
#define put_fix(a, n) cout << fixed << setprecision(n) << a << "\n"

#define ll long long
#define ldb long double
#define db double

#define sqr(x) (x*x)

#define fto(i, a, b) for (int i = a; i <= b; ++i)
#define fdto(i, b, a) for (int i = b; i >= a; --i)

#define sz(a) (int) (a.size())

#define di deque <int>
#define vi vector <int>
#define vl vector <long long>

#define pii pair <int, int>
#define vii vector <int, int>
#define vpii vector<pair<int, int>>

#define pf push_front
#define pb push_back
#define ppf pop_front
#define ppb pop_back
#define eb emplace_back
#define mp make_pair
#define ff first
#define ss second

#define oo 1000000007
#define OO 1000000000000000007

#define eps 0.0000000001
#define mod 
#define maxN 200005
#define maxM 10000005

using namespace std;

int n, a[maxN];

void sub_1() {
    for (int i = 2; i <= n; ++i) {
        int pos = 0;
        for (int j = i-1; j >= 1; --j) {
            if (a[j] == a[i]) {
                pos = j;
                break;
            }
        }

        if (pos) {
            for (int j = pos+1; j <= i-1; ++j) a[j] = a[i];
        }
    }

    for (int i = 1; i <= n; ++i) cout << a[i] << "\n";
}

void sub_2() {
    int mn_1 = oo, mn_2 = oo;
    int mx_1 = 0, mx_2 = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 1) {
            mn_1 = min(mn_1, i);
            mx_1 = max(mx_1, i);
        }
        else {
            mn_2 = min(mn_2, i);
            mx_2 = max(mx_2, i);
        }
    }

    if (mn_1 < mn_2) {
        for (int i = 1; i <= n; ++i) {
            if (i <= mx_1) cout << "1\n";
            else cout << a[i] << "\n";
        }
    }
    else {
        for (int i = 1; i <= n; ++i) {
            if (i <= mx_2) cout << "2\n";
            else cout << a[i] << "\n";
        }
    }
}

int st_val[maxN];
map<int, int> far;
void sub_3() {
    for (int i = n; i >= 1; --i) {
        if (far.count(a[i]) == 0) far[a[i]] = i;
    }
    // for (int i = 1; i <= n; ++i) cout << far[a[i]] << " ";
    int pos = 1;
    while (1) {
        if (pos > n) break;
        if (far[a[pos]] > pos) {
            st_val[pos] = a[pos];
            pos = far[a[pos]] + 1;
        }
        else {
            st_val[pos] = a[pos];
            ++pos;
        }
    }

    bool ok = false;
    int val = 0;
    for (int i = 1; i <= n; ++i) {
        if (st_val[i]) {
            ok = true;
            val = st_val[i];
        }

        if (!ok) cout << a[i] << "\n";
        else cout << val << "\n";
    }
}

int main () {
    // #ifndef ONLINE_JUDGE
        // freopen("test.inp", "r", stdin);
        // freopen("test.out", "w", stdout);
    // #endif // ONLINE_JUDGE
    FAST;

    cin >> n;
    bool ok_o = false;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] != 1 && a[2] != 2) ok_o = true;
    }

    sub_3();

    // if (n <= 10000) sub_1();
    // else if (!ok_o) sub_2();
    // else sub_3();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:146:10: warning: variable 'ok_o' set but not used [-Wunused-but-set-variable]
  146 |     bool ok_o = false;
      |          ^~~~

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40