Submission #441524

#	Time	Username	Problem	Language	Result	Execution time	Memory
441524		elazarkoren	Exam (eJOI20_exam)	C++17	0 / 100	115 ms	580 KiB

exam

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#define x first
#define y second
#define chkmin(a, b) a = min(a, b)
#define all(v) v.begin(), v.end()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 1e5 + 1;

int a[MAX_N], b[MAX_N];

int n;

int Count(vi &v, int l, int r) {
    int ans = 0;
    for (int i = l; i < r; i++) {
        if (v[i] == b[i]) ans++;
    }
    return ans;
}

int main() {
    cin >> n;
    set<int> visited;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) cin >> b[i];
    vi id(n);
    for (int i = 0; i < n; i++) {
        id[i] = i;
    }
    sort(all(id), [&] (int i, int j) {
        return b[i] < b[j];
    });
//    int ans = 0;
    vi dp1(n), dp2(n);
    vi dp_next1(n), dp_next2(n);
    for (int i = 0; i < n; i++) dp1[i] = dp2[i] = a[i];
    for (int i = id[0]; i < n; i++) {
        if (a[id[i]] == b[id[0]]) {
            for (int j = id[0]; j < i; j++) {
                dp1[j] = a[id[i]];
            }
            break;
        }
    }
//    vi ans_dp1(n), ans_dp2(n);
//    ans_dp2[0] = a[id[0]] == b[id[0]];
    for (int i = 1; i < n; i++) {
        int count1 = Count(dp1, 0, n);
        int count2 = Count(dp2, 0, n);
        int ind = n;
        for (int j = id[i]; j < n; j++) {
            if (a[id[j]] == b[id[i]]) {
                ind = j + 1;
                for (int k = id[0]; k < i; k++) {
                    dp_next1[k] = a[id[i]];
                }
                break;
            }
        }
        if (Count(dp1, 0, id[i]) + Count(dp1, ind, n) > Count(dp2, 0, id[i]) + Count(dp2, ind, n)) {
            for (int j = 0; j < id[i]; j++) {
                dp_next1[j] = dp1[j];
            }
            for (int j = ind; j < n; j++) {
                dp_next1[j] = dp1[j];
            }
        } else {
            for (int j = 0; j < id[i]; j++) {
                dp_next1[j] = dp2[j];
            }
            for (int j = ind; j < n; j++) {
                dp_next1[j] = dp2[j];
            }
        }
        if (count1 > count2) {
            swap(dp1, dp2);
        }
        swap(dp_next1, dp1);
    }
    cout << max(Count(dp1, 0, n), Count(dp2, 0, n));
//    int ans = a[0] == b[0];
//    for (int i = 1; i < n; i++) {
//        int count = a[i] == b[i];
//        int best_count = a[i] == b[i], ind = i;
//        for (int j = i - 1; j >= 0; j--) {
//            if (a[j] == b[j]) count--;
//            if (a[i] == b[j]) count++;
//            if (count > best_count) {
//                best_count = count;
//                ind = j;
//            }
//        }
//        for (int j = i - 1; j >= ind; j--) a[j] = a[i];
//        ans += best_count;
//    }
//    cout << ans;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22