[Codeforces] Array Craft [C++]

 

 

#문제 간단 정리

prefix 와 subfix 가 존재하고

prefix 는 x 까지 이전의 값들끼리 더했을때 최대가 되는 인덱스

subfix 는 y 이후 값들끼리 더했을 떄 최대가 되는 인덱스

y<x 로 주어진다

 

n길이의 배열로 n x y를 만족하는

배열을 구하라(반드시 존재함)

 

#문제 해결 방법

 

우선 x<y 기 때문에

x와 y 사이에는 무조건 1로 채워주는 게 배열을 만들기 가장 쉽다.

왜냐면 가운데는 두 서브픽스와 프리픽스 전부다 영향을 주기 때문이다.

 

그래서 x 이후에는 감소해야 prefix 가 고정되기 때문에

변갈아서 -1 로 바꿔주고

y 이전에도 번갈아서 -1로 바꿔준다

번갈아서 -1을 해주지 않을 경우에는 반례가 존재하기에 

번갈아서 바꿔줘야한다.

12 7 6 같은 경우가 존재 할 수 있다. (번갈아서 안바꾸면)

 

#전체 코드

#include <iostream>
#include <vector>
using namespace std;


int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, x, y;
        cin >> n >> x >> y;
        vector<int> a(n, 1);

        // x 이후의 1의 개수보다 -1의 개수가 많아야 한다
        for (int i = x; i < n; i += 2) {
            a[i] = -1;
        }

        // y 이전의 1의 개수보다 -1의 개수가 많아야 한다
        for (int i = y-2; i >=0; i -= 2) {
            a[i] = -1;
        }


        for (int i = 0; i < n; ++i) {
            cout << a[i] << " ";
        }
        cout << endl;
    }

    return 0;
}