求助 CF C2
  • 板块学术版
  • 楼主Iamzzr
  • 当前回复6
  • 已保存回复6
  • 发布时间2022/10/23 17:51
  • 上次更新2023/10/27 06:16:47
查看原帖
求助 CF C2
527243
Iamzzr楼主2022/10/23 17:51

第二个点错了,代码:

#include <iostream>

using namespace std;

const int N = 200010;

int T;
int a[N];
int l[N], r[N];
int dis[N];
int L[N], R[N];
int Next[N];

int main() {
    cin >> T;
    while (T--) {
        int n; cin >> n;
        int num = 0, m = n, last = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            if (a[i] == 0) num++;
            if (a[i] != 0) Next[last] = i, last = i;
        }
        Next[last] = n + 1;
        if ((n - num) & 1) { cout << -1 << "\n"; continue; }
        if (!(n - num)) { cout << 1 << "\n" << 1 << " " << n << "\n"; continue; }
        int ans = 0;
        for (int i = Next[0]; i <= n; i = Next[i], i = Next[i]) {
            int x = a[i], y = a[Next[i]];
            if (x != y) {
                ans++, l[ans] = i, r[ans] = i;
                if (i + 1 != Next[i]) ans++, l[ans] = i + 1, r[ans] = Next[i] - 1;
                ans++, l[ans] = Next[i], r[ans] = Next[Next[i]] - 1;
            }
            else {
                if (i + 1 == Next[i]) {
                    ans++, l[ans] = i, r[ans] = Next[i] - 1;
                }
                else {
                    ans++, l[ans] = i, r[ans] = i;
                    if (i + 2 != Next[i]) ans++, l[ans] = i + 1, r[ans] = Next[i] - 2;
                    ans++, l[ans] = Next[i] - 1, r[ans] = Next[Next[i]] - 1;
                }
            }
        }
        bool flag = false;
        if (l[1] != 1) {
            flag = true;
            ans++;
        }
        cout << ans << "\n";
        if (flag) cout << 1 << " " << l[1] - 1 << "\n";
        for (int i = 1 + flag; i <= ans; i++) cout << l[i] << " " << r[i] << "\n";        
        // n = num;
        // if (!n) { cout << 1 << "\n" << 1 << " " << m << "\n"; continue; }
        // if (n & 1) { cout << -1 << "\n"; continue; }
        // int ans = 0;
        // for (int i = 1; i <= n; i += 2) {
        //     int x = a[i], y = a[i + 1];
        //     if (x == y) {
        //         if ((dis[i] & 1) != (dis[i + 1] & 1)) ans++, l[ans] = dis[i], r[ans] = dis[i + 1];
        //         else {
        //             ans++;
        //             l[ans] = dis[i], r[ans] = dis[i], ans++, l[ans] = dis[i + 1], r[ans] = dis[i + 1];
        //         }
        //     }
        //     else {
        //         if (!((dis[i] & 1) != (dis[i + 1] & 1))) ans++, l[ans] = dis[i], r[ans] = dis[i + 1];
        //         else {
        //             ans++;
        //             l[ans] = dis[i], r[ans] = dis[i], ans++, l[ans] = dis[i + 1], r[ans] = dis[i + 1];
        //         }
        //     }
        // }
        // int cnt = 0;
        // for (int i = 1; i <= ans; i++) {
        //     if (l[i] != r[i - 1] + 1) {
        //         cnt++, L[cnt] = r[i - 1] + 1, R[cnt] = l[i] - 1;
        //     }
        //     cnt++, L[cnt] = l[i], R[cnt] = r[i];
        // }
        // cout << cnt << "\n";
        // for (int i = 1; i <= cnt; i++) cout << L[i] << " " << R[i] << "\n";
    }
    return 0;
}

2022/10/23 17:51
加载中...