제출 #1310491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310491		olizarowskib	Parking (CEOI22_parking)	C++20	20 / 100	79 ms	139076 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define ft first
#define sc second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int, int>
#define vi vector<int>
#define tii tuple<int, int, int>
#define tiii tuple<int, int, int, int>
#define tiiii tuple<int, int, int, int, int>
#define vpi vector<pi>
#define vtii vector<tii>
#define vtiii vector<tiii>

const int N = (1 << 20), MOD = 1e9 + 7, INF = int(1e18);

int arr[N], poz[N], k[N], wsk[N], cnt, e;
bool vis[N], gd[N], st[N];

int md(int x, int p){
    if(x <= p) return x;
    return x - p;
}

int oth(int x, int p){
    if(x <= p) return x + p;
    return x - p;
}

bool empt(int x){return (arr[x] == 0);}

queue<int> cur;

int psh(){
    while(!cur.empty() && !empt(cur.front())) cur.pop();
    if(cur.empty()) return -1;
    return cur.front();
}

vpi ans;
vi z[N];

void mv(int x, int p, int n, int m){
    int a = poz[x];
    p = md(p, m);
    ans.pb({md(a, m), p});
    if(a > m) cur.push(a);
    arr[a] = 0;
    if(!empt(p + m)){
        gd[md(x, n)] = 1;
        cnt--;
    }else p += m;
    poz[x] = p;
    arr[p] = x;
}

void check_clr(int x, int n, int m){
    int c = md(x, n);
    if(gd[c]) return;
    int y = oth(x, n);
    int a = poz[x], b = poz[y];
    if(a > m && !empt(a - m)) return;
    if(b > m && !empt(b - m)) return;
    if(max(a, b) <= m) return;
    if(a > m){
        swap(a, b);
        swap(x, y);
    }
    mv(x, b, n, m);
    if(a <= m) check_clr(arr[a + m], n, m);
}

int dfs(int x, int n, int m){
    if(vis[x]){
        if(k[x] == 0) k[x] = x;
        return k[x];
    }
    int u = poz[x];
    vis[x] = 1;
    if(u <= m){
        wsk[x] = arr[u + m];
        st[wsk[x]] = 1;
        return k[x] = dfs(wsk[x], n, m);
    }
    int y = oth(x, n);
    wsk[x] = y;
    st[y] = 1;
    if(poz[y] > m) return k[x] = y;
    return k[x] = dfs(y, n, m);
}

void check_cmp(int x, int n, int m){
    x = md(x, n);
    if(z[x].empty() || gd[x]) return;
    int a = z[x][0], b;
    if(z[x].size() < 2) b = a;
    else b = z[x][1];
    if(!gd[md(a, n)] && poz[a] <= m){
        e = psh();
        int p = poz[a];
        mv(a, e, n, m);
        check_clr(a, n, m);
        check_clr(arr[p + m], n, m);
        if(!st[oth(a, n)]) check_cmp(k[oth(a, n)], n, m);
    }
    if(!gd[md(b, n)] && poz[b] <= m){
        e = psh();
        int p = poz[b];
        mv(b, e, n, m);
        check_clr(b, n, m);
        check_clr(arr[p + m], n, m);
        if(!st[oth(b, n)]) check_cmp(k[oth(b, n)], n, m);
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    // random_device rd;
    // mt19937_64 gen(rd());
    int n, m;
    cin >> n >> m;
    cnt = n;
    for(int i = 1; i <= m; i++){
        cin >> arr[i + m] >> arr[i];
        if(vis[arr[i]]) arr[i] += n;
        if(arr[i] != 0) vis[arr[i]] = 1;
        if(vis[arr[i + m]]) arr[i + m] += n;
        vis[arr[i + m]] = 1;
        poz[arr[i]] = i;
        poz[arr[i + m]] = i + m;
        vis[0] = 0;
    }
    gd[0] = 1;
    for(int i = 1; i <= n; i++){
        vis[i] = vis[i + n] = 0;
        if(md(poz[i], m) == md(poz[i + n], m)){
            gd[i] = 1;
            cnt--;
        }
        check_clr(i, n, m);
    }
    for(int i = 1; i <= m; i++) cur.push(i + m);
    if(cnt > 0 && psh() < 0){
        cout << "-1\n";
        return 0;
    }
    for(int i = 1; i <= 2 * n; i++){
        if(poz[i] <= m && !gd[i]) dfs(i, n, m);
    }
    for(int i = 1; i <= 2 * n; i++){
        if((st[i] && k[i] != i) || gd[md(i, n)]) continue;
        if(k[i] == i){
            e = psh();
            int a = poz[i];
            mv(i, e, n, m);
            check_clr(i, n, m);
            check_clr(arr[a + m], n, m);
        }else z[md(k[i], n)].pb(i);
    }
    for(int i = 1; i <= n; i++){
        if(z[i].size() < 2 || md(z[i][0], n) == md(z[i][1], n)) check_cmp(i, n, m);
    }
    e = psh();
    while(!cur.empty() && cur.front() == e) cur.pop();
    if(cnt > 0 && psh() < 0){
        cout << "-1\n";
        return 0;
    }
    cur.push(e);
    for(int i = 1; i <= n; i++) check_cmp(i, n, m);
    
    cout << int(ans.size()) << "\n";
    // for(auto [i, j] : ans) cout << i << ' ' << j << "\n";
    return 0;
}

• Subtask 1: 2 / 10
• Subtask 2: 2 / 10
• Subtask 3: 5 / 25
• Subtask 4: 3 / 15
• Subtask 5: 5 / 25
• Subtask 6: 3 / 15