BOJ 9567 Empty Stalls

https://www.acmicpc.net/problem/9567

9567번: Empty Stalls

 

입력이 조금 귀찮게 들어오는데, 각 쿼리 당 $XY$ 마리의 소가 선호하는 stall이 입력으로 주어집니다. 최대 $N-1$ 마리의 소가 선호하는 stall이 입력으로 들어왔을 때, 비게 되는 가장 작은 stall의 번호를 출력하는 문제입니다.

 

N의 범위가 크기 때문에, 각 쿼리를 입력 받으면서 소를 배치해주는 방식은 시간초과가 발생합니다. 이를 해결하기 위해 먼저 모든 쿼리를 미리 받아 각 stall마다 선호하는 소가 몇 마리 있는지를 저장해두고, stall을 0번부터 순회하며 소를 배정해줍니다. 이후 다시 한 번 stall을 순회하며 빈 stall을 찾아줍니다. 이 경우 $\mathcal{O}(N)$의 시간에 해결할 수 있습니다.

 

각 소가 어떠한 순서로 barn에 도착하더라도 정답에는 변화가 없다는 것을 알면(=문제에서 주어짐) 쉽게 풀 수 있는 문제였던 것 같습니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>

#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
#define int long long

using namespace std;

int T, n, k, arr[3000010];

int32_t main(void) {
    FastIO;

#ifdef HN
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    T = 1;
    //cin >> T;

    while (T--) {
        cin >> n >> k;

        for (int i = 0; i < k; i++) {
            int x, y, a, b;
            cin >> x >> y >> a >> b;
            for (int j = 1; j <= y; j++) {
                int tmp = (j * a) % n;
                tmp = (tmp + b) % n;
                arr[tmp] += x;
            }
        }

        int cows = 0;
        for (int i = 0; i < 2 * n; i++) {
            int idx = i % n;
            if (arr[idx]) {
                cows += arr[idx] - 1;
                arr[idx] = 1;
            } else if (cows) {
                cows--;
                arr[idx] = 1;
            }
        }

        int ans = n - 1;
        for (int i = 0; i < n; i++) {
            if (!arr[i]) {
                ans = i;
                break;
            }
        }

        cout << ans << endl;
    }

    return 0;
}