[Codeforces]Round #731. C

C. Pair Programming

문제 출처: https://codeforces.com/contest/1547/problem/C

문제 요약

초기에 입력으로 주어지는 k만큼의 줄을 가진 파일이 있다. Monocarp(M) 와 Polycarp(P) 는 각각 n분과 m분동안 일련의 ‘작업’을 하는데, 이 작업을 나타낸 수열이 a_n과 b_m이다.
- a_i 가 0 이면 파일에 한 줄을 추가하는 작업을 한다.
- a_i 가 0보다 크다면 파일의 a_i 번째 줄을 수정한다.
당연히, 존재하지 않는 줄을 수정할 수는 없다. 또한, i < j 일 때 a_j 가 a_i 보다 먼저 실행될 수는 없다. M과 P가 작업을 하는 가능한 sequence를 출력하라. 불가능하다면 -1을 출력하라.

Let’s look at an example. Suppose k= 3. Monocarp first changed the line with the number 2 and then added a new line (thus, n = 2, a = [2, 0]). Polycarp first added a new line and then changed the line with the number 55 (thus, m=2,b=[0,5]m=2,b=[0,5]).

Since the initial length of the file was 3, in order for Polycarp to change line number 5 two new lines must be added beforehand. Examples of correct sequences of changes, in this case, would be [0,2,0,5] and [2,0,0,5]. Changes [0,0,5,2] (wrong order of actions) and [0,5,2,0] (line 5 cannot be edited yet) are not correct.

Example

input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
5 3 2 2 2 0 0 5 4 3 2 2 0 5 0 6 0 2 2 1 0 2 3 5 4 4 6 0 8 0 0 7 0 9 5 4 1 8 7 8 0 0
output
1
2
3
4
5
2 0 0 5 0 2 0 6 5 -1 0 6 0 7 0 8 0 9 -1
문제 풀이

처음엔 DFS 이용해서 최적해를 찾는 문제인 줄 알았지만 마지막 tc에서 시간초과 났다.

단순히 빨리 풀 방법을 생각해보니 그리디로 풀리는 문제였다. a_i 와 b_j 중에서 다음에 올 작업을 선택할 때, 0이 있다면 무조건 선택하는 것이 전체 solution에 도움이 된다. 따라서 0이 있다면 무조건 선택하고, 0이 아니라해도 파일의 line 수보다 적으면 선택하는 것이 그 다음 선택을 하는데에 어떠한 영향도 주지 않기 때문이다.
풀이 코드

#include <bits/stdc++.h>
#define INF 1e9
#define ll long long
#define pii pair<int, int> 
#define vi vector<int> 
#define foi(n) for(int i=0;i<n;++i)
#define endl '\n'
using namespace std;
 
int t;
int k,n,m;
int a_opr[101];
int b_opr[101];
 
void solve(){
    bool possible=true;
    vi path;
    int cur_line_num=k;
    int a_idx=0, b_idx=0;
    
    while(a_idx!=n || b_idx!=m){
        if(a_idx!=n && a_opr[a_idx]==0){
            path.push_back(a_opr[a_idx++]);
            k++;
        }
        else if(a_idx!=n && a_opr[a_idx]<=k){
            path.push_back(a_opr[a_idx++]);
        }
        else if(b_idx!=m && b_opr[b_idx]==0){
            path.push_back(b_opr[b_idx++]);
            k++;
        }
        else if(b_idx!=m && b_opr[b_idx]<=k){
            path.push_back(b_opr[b_idx++]);
        }
        else{   //not possible
            possible=false;
            break;
        }
    }
    if(possible){
        for(auto e:path) cout<<e<<' ';
        cout<<endl;
    }
    else cout<<"-1\n";
}
 
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
 
    cin>>t;
    while(t--){
        cin>>k>>n>>m;
        foi(n) cin>>a_opr[i];
        foi(m) cin>>b_opr[i];
        solve();
    }
}

C. Pair Programming

문제 요약

문제 풀이

풀이 코드