AtCoder Grand Contest 019

Submission #1540293

Source codeソースコード

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using namespace std;

string s1;
string s2;


const int MAXN = 2001;

int l[MAXN], r[MAXN];

pair <int, int> a[MAXN];
int ac = 0;
int n;

int m(int x) {
    x %= n;
    return (x >= 0) ? x : x + n;
}

int main() {
#ifdef PAUNSVOKNO
	freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20);
    cin >> s1 >> s2;
    n = s1.length();
    int c1 = 0, c2 = 0;
    for (int i = 0; i < n; i++) {
        if (s1[i] == '1') c1++;
    }

    for (int i = 0; i < n; i++)
        if (s2[i] == '1') c2++;

    if (c1 && !c2) {
        cout << -1 << "\n";
        return 0;
    }

    if (s1 == s2) {
        cout << 0 << "\n";
        return 0;
    }

    for (int i = 0; i < n; i++) {
        for (l[i] = 0; s2[m(i - l[i])] == '0'; l[i]++);
        for (r[i] = 0; s2[m(i + r[i])] == '0'; r[i]++);
    }

    int ans = MAXN * MAXN;

    for (int d = -n; d < n; d++) {
        ac = 0;
        int adc = 0;

        for (int i = 0; i < n; i++) {
            int ni = (i + n + d) % n;
            if (s1[i] == s2[ni]) continue;
            adc++;
            int nl = l[i] - max(-d, 0);
            int nr = r[i] - max(d, 0);
            if ((nl >= 0) && (nr >= 0)) a[ac++] = { nl, nr };
        }

        int cur = MAXN * MAXN;
        sort(a, a + ac);
        int mx = 0;

        for (int i = ac - 1; i >= 0; i--) {
            cur = min(cur, a[i].first + mx);
            mx = max(mx, a[i].second);
        }

        cur = min(cur, mx);

        ans = min(ans, abs(d) + cur * 2 + adc);
    }

    cout << ans << "\n";
}

Submission

Task問題 D - Shift and Flip
User nameユーザ名 lhicpetuh
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1000
Source lengthソースコード長 1761 Byte
File nameファイル名
Exec time実行時間 135 ms
Memory usageメモリ使用量 384 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt,sample_04.txt
All 1000 / 1000 sample_01.txt,sample_02.txt,sample_03.txt,sample_04.txt,sample_01.txt,sample_02.txt,sample_03.txt,sample_04.txt,subtask_1_01.txt,subtask_1_02.txt,subtask_1_03.txt,subtask_1_04.txt,subtask_1_05.txt,subtask_1_06.txt,subtask_1_07.txt,subtask_1_08.txt,subtask_1_09.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_12.txt,subtask_1_13.txt,subtask_1_14.txt,subtask_1_15.txt,subtask_1_16.txt,subtask_1_17.txt,subtask_1_18.txt,subtask_1_19.txt,subtask_1_20.txt,subtask_1_21.txt,subtask_1_22.txt,subtask_1_23.txt,subtask_1_24.txt,subtask_1_25.txt,subtask_1_26.txt,subtask_1_27.txt,subtask_1_28.txt,subtask_1_29.txt,subtask_1_30.txt,subtask_1_31.txt,subtask_1_32.txt,subtask_1_33.txt,subtask_1_34.txt,subtask_1_35.txt,subtask_1_36.txt,subtask_1_37.txt,subtask_1_38.txt,subtask_1_39.txt,subtask_1_40.txt,subtask_1_41.txt,subtask_1_42.txt,subtask_1_43.txt,subtask_1_44.txt,subtask_1_45.txt,subtask_1_46.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 256 KB
subtask_1_03.txt AC 1 ms 256 KB
subtask_1_04.txt AC 1 ms 256 KB
subtask_1_05.txt AC 40 ms 256 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 1 ms 256 KB
subtask_1_08.txt AC 1 ms 256 KB
subtask_1_09.txt AC 1 ms 256 KB
subtask_1_10.txt AC 1 ms 256 KB
subtask_1_11.txt AC 92 ms 256 KB
subtask_1_12.txt AC 89 ms 256 KB
subtask_1_13.txt AC 92 ms 256 KB
subtask_1_14.txt AC 135 ms 256 KB
subtask_1_15.txt AC 122 ms 256 KB
subtask_1_16.txt AC 108 ms 256 KB
subtask_1_17.txt AC 105 ms 256 KB
subtask_1_18.txt AC 99 ms 384 KB
subtask_1_19.txt AC 96 ms 256 KB
subtask_1_20.txt AC 93 ms 256 KB
subtask_1_21.txt AC 96 ms 256 KB
subtask_1_22.txt AC 98 ms 256 KB
subtask_1_23.txt AC 109 ms 256 KB
subtask_1_24.txt AC 109 ms 256 KB
subtask_1_25.txt AC 109 ms 256 KB
subtask_1_26.txt AC 1 ms 256 KB
subtask_1_27.txt AC 2 ms 256 KB
subtask_1_28.txt AC 6 ms 256 KB
subtask_1_29.txt AC 22 ms 256 KB
subtask_1_30.txt AC 82 ms 256 KB
subtask_1_31.txt AC 1 ms 256 KB
subtask_1_32.txt AC 1 ms 256 KB
subtask_1_33.txt AC 2 ms 256 KB
subtask_1_34.txt AC 6 ms 256 KB
subtask_1_35.txt AC 22 ms 256 KB
subtask_1_36.txt AC 85 ms 256 KB
subtask_1_37.txt AC 1 ms 256 KB
subtask_1_38.txt AC 2 ms 256 KB
subtask_1_39.txt AC 6 ms 256 KB
subtask_1_40.txt AC 22 ms 256 KB
subtask_1_41.txt AC 82 ms 256 KB
subtask_1_42.txt AC 81 ms 256 KB
subtask_1_43.txt AC 82 ms 256 KB
subtask_1_44.txt AC 87 ms 256 KB
subtask_1_45.txt AC 85 ms 256 KB
subtask_1_46.txt AC 87 ms 256 KB