[BOJ] 8146 Tetris Attack

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

8146번: Tetris Attack

일단 여러가지 관찰을 해본게 있는데, 

1. \(x..y..x..y\)의 경우엔, \(x..x...y..y\) 경우가 되거나 \(x..y..y..x\) 경우가 되거나 \(y..x..x..y\) 경우가 된다.

2. \(x..ab..cd..x\)의 경우에는, 오른쪽 \(x\)를 모두 왼쪽으로 밀고 생각해도 된다. (증명은 쉽게 가능하다.)

3. 1에서 2를 덧붙여 생각해보면, \(x..x..y..y\)의 경우로만 만들어도 최소 횟수를 만족할 수 있다.

 

이제 여기까지 왔다면 다 풀었다.

두번 등장한 가장 빠른 수를 \(x\)라 할때, \(xSx\) 에서 \(S\)에는 두 번 이상 등장하는 수가 없기 때문에, 오른쪽 \(x\)를 왼쪽으로 쭉 밀어 \(xxS\)의 형태로 만들며 진행해줄 수 있다.

스택으로 쉽게 구현이 가능했다. 시간복잡도는 \(O(N)\)

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const int TMX = 1 << 18;
const long long llINF = 1e18;
const long long mod = 1e9+7;
const long long hashmod = 100003;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,top,c[50005];
pi s[50005];

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    vec ans;
    for(int i = 1;i <= 2*n;i++) {
        int x; cin >> x;
        if(!c[x]) {
            top++;
            s[top] = {x,top};
            c[x] = 1;
        }
        else {
            vecpi pu;
            while(s[top].x^x) {
                pu.pb({s[top].x,s[top].y-1});
                ans.pb(s[top].y);
                top--;
            }
            top--;
            reverse(all(pu));
            for(pi i : pu) s[++top] = i;
        }
    }
    cout << ans.size() << '\n';
    for(int i : ans) cout << i << '\n';
}