Codeforces Round #669 (Div. 2) ABC

from sys import stdin
def input(): return stdin.readline().rstrip()
 
for _ in range(int(input())):
    l = int(input())
    s = list(map(int, input().split()))
    r = []
 
    for i in range(l//2):
        if s[i*2] == 0 and s[i*2+1] == 0:
            r.append(0); r.append(0);
        elif s[i*2] == 1 and s[i*2+1] == 1:
            r.append(1); r.append(1);
        else:
            r.append(0);
 
    print(len(r))
    print(*r)

 

A - Ahahahahahahahaha

 

입력의 길이가 반드시 2n이라는 점에 근거하여 두 자리씩 끊어서 보자.

 

00과 11은 결과에 영향을 미치지 않으니 그대로 있어도 좋다.

01과 10은 홀수, 짝수 indices의 합이 서로 다르게 만들 위험이 존재한다. 따라서, 1을 제외하고 0만 남긴다.

 

위와 같이 구현하면 아무리 많은 1을 지워도 길이는 항상 n 이상이 된다.

 

 

#include <bits/stdc++.h>
using namespace std;

int N, arr[1001];
bool used[1001];

vector<int> ans;

int gcd(int a, int b) {
    int n;
    if (a < b) swap(a, b);
    while (b != 0) {
        n = a % b;
        a = b;
        b = n;
    }
    return a;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int TEST; cin >> TEST;
    while (TEST--) {
        ans.clear();
        cin >> N;

        for (int i = 0; i < N; ++i) {
            cin >> arr[i];
            used[i] = 0;
        }

        sort(arr, arr + N);
        ans.push_back(arr[N - 1]);
        used[N - 1] = 1;

        while (ans.size() != N) {
            int mx = 0, ind = 0;
            for (int i = 0; i < N; ++i) {
                if (used[i]) continue;
                int temp = arr[i];
                for (int i = 0; i < ans.size(); ++i) {
                    temp = gcd(temp, ans[i]);
                }
                if (temp > mx) {
                    mx = temp;
                    ind = i;
                }
            }
            ans.push_back(arr[ind]);
            used[ind] = 1;
        }
        for (int i = 0; i < ans.size(); ++i) {
            cout << ans[i] << " ";
        }
        cout << "\n";
    }

    return 0;
}

 

B - Big Vova

 

문제에서 설명한대로 열심히 구현하면 된다. B₀, B₁, ..., B_i-1 까지의 gcd를 구하고 B_i 와 그의 gcd를 구하는 식으로 하면 훨씬 빠를 것이다. (550ms가 떴다..)

 

 

#include <bits/stdc++.h>
using namespace std;

int arr[10001];
int know = 0;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N; cin >> N;
    if (N == -1) return 0;
    int lq = 1, rq = 2;

    if (N == 1) {
        cout << "! 1" << "\n" << endl;
        return 0;
    }

    for (int i = 1; i <= 2 * N; ++i) {
        int ret1, ret2;

        cout << "? " << lq << " " << rq << "\n" << endl;
        cin >> ret1;
        if (ret1 == -1) return 0;
        cout << "? " << rq << " " << lq << "\n" << endl;
        cin >> ret2;
        if (ret2 == -1) return 0;

        if (ret1 > ret2) {
            arr[lq] = ret1;
            lq = rq;
            rq++;
            know++;
        }
        else {
            arr[rq] = ret2;
            rq++;
            know++;
        }

        if (rq > N) {
            break;
        }

        if (know == N) break;
    }

    cout << "! ";
    for (int i = 1; i <= N; ++i) {
        if (arr[i] == 0) cout << N << " ";
        else cout << arr[i] << " ";
    }
    cout << "\n" << endl;


    return 0;
}

 

C - Chocolate Bunny

 

정답 수열이 위와 같은 형태라고 하자.

 

A mod B = p, B mod A = q 일 때 max(p, q) = min(A, B) 이다.

p가 더 크다면 A, q가 더 크다면 B의 값을 확신할 수 있다.

 

질의를 할 때 투포인터를 활용하였다. 왼쪽 포인터는 lp, 오른쪽 포인터는 rp라고 하자.

lp를 index-1, rp를 index-2에 놓고 시작한다. ? A B와 ? B A 이렇게 두 번의 질의를 해서 A와 B 중 하나를 확정 짓는다.

 

A가 확정되었다면 lp를 B에, rp를 C에 두고 반복한다. B가 확정되었다면 rp를 C에 두고 반복한다.

 

이렇게 하면 마지막에 모르는 값이 하나 남는데, 그 값은 반드시 수열에서 제일 큰 값이다.