제출 #1246766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246766		vht2025	Fliper (COCI22_fliper)	C++20	0 / 110	382 ms	82648 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Edge{
    int to, id;
};

const int DIRS = 4;           // 0 E,1 S,2 W,3 N
int refl[2][DIRS] = {         // [type 0:'/', 1:'\\'][in] = out
    {3, 2, 1, 0},             // '/'
    {1, 0, 3, 2}              // '\'
};

int opposite(int d){ return d ^ 2; }

/* ---------- step 0: input ---------- */
struct Ob{
    int x, y;
    char t;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin>>n)) return 0;
    vector<Ob> a(n);
    for(int i=0;i<n;++i) cin>>a[i].x>>a[i].y>>a[i].t;

    /* ---------- step 1: nearest neighbours row/col ---------- */
    unordered_map<long long, vector<pair<int,int>>> rows, cols;
    rows.reserve(n*2); cols.reserve(n*2);
    auto hrow=[&](int y){ return (ll)y; };
    auto hcol=[&](int x){ return (ll)x; };
    for(int i=0;i<n;++i){
        rows[hrow(a[i].y)].push_back({a[i].x,i});
        cols[hcol(a[i].x)].push_back({a[i].y,i});
    }
    vector<array<int,DIRS>> nxt(n);
    const int NIL=-1;
    for(auto &v:rows){
        auto &vec=v.second;
        sort(vec.begin(),vec.end());
        for(int k=0;k<(int)vec.size();++k){
            int id=vec[k].second;
            nxt[id][2]= (k? vec[k-1].second : NIL);           // W
            nxt[id][0]= (k+1<(int)vec.size()? vec[k+1].second : NIL); // E
        }
    }
    for(auto &v:cols){
        auto &vec=v.second;
        sort(vec.begin(),vec.end());
        for(int k=0;k<(int)vec.size();++k){
            int id=vec[k].second;
            nxt[id][3]= (k? vec[k-1].second : NIL);           // N
            nxt[id][1]= (k+1<(int)vec.size()? vec[k+1].second : NIL); // S
        }
    }

    /* ---------- step 2: build next-state function ---------- */
    const int S = 4*n;
    auto idx = [&](int i,int d){ return i*4+d; };
    vector<int> go(S, -1);
    for(int i=0;i<n;++i){
        int tp = (a[i].t=='\\');
        for(int d=0;d<DIRS;++d){
            int out = refl[tp][d];
            int j = nxt[i][out];
            if(j==NIL) continue;               // goes to infinity
            int nd = opposite(out);
            go[idx(i,d)] = idx(j,nd);
        }
    }

    /* ---------- step 3: detect cycles ---------- */
    vector<int> col(S,0), cycId(S,-1);
    vector<int> cycLen;               // length of each cycle
    int cid=0;
    vector<int> st;
    bool bad=false;
    for(int v=0;v<S && !bad;++v) if(!col[v]){
        int x=v;
        while(x!=-1 && !col[x]){
            col[x]=1; st.push_back(x);
            x=go[x];
        }
        if(x!=-1 && col[x]==1){               // found a new cycle
            vector<int> cyc;
            int y;
            do{
                y=st.back(); st.pop_back();
                cyc.push_back(y);
            }while(y!=x);
            int L=cyc.size();
            if(L%8){ bad=true; break; }
            for(int z:cyc) cycId[z]=cid;
            cycLen.push_back(L); ++cid;
        }
        while(!st.empty()){ col[st.back()]=2; st.pop_back(); }
    }
    if(bad){ cout<<-1<<"\n"; return 0; }

    const int DUMMY = cid;                 // node index of ∞
    int V = cid+1;

    /* ---------- step 4: build cycle-graph ---------- */
    struct EInfo{ int u,v,obs; };
    vector<vector<Edge>> g(V);
    vector<EInfo> einfo; einfo.reserve(n);
    for(int i=0;i<n;++i){
        int c1=-2,c2=-2;           // collect ≤2 different cycle ids
        for(int d=0;d<DIRS;++d){
            int s=idx(i,d);
            int c=cycId[s];
            if(c==-1) continue;    // this state flies to ∞
            if(c1==-2||c1==c) c1=c;
            else c2=c;
        }
        if(c1==-2){                // no cycle at all
            einfo.push_back({DUMMY,DUMMY,i});
            continue;
        }
        if(c2==-2){                // only one cycle
            einfo.push_back({c1,DUMMY,i});
        }else{
            einfo.push_back({c1,c2,i});
        }
    }
    int m=einfo.size();
    for(int id=0;id<m;++id){
        auto [u,v,obs]=einfo[id];
        g[u].push_back({v,id});
        if(u!=v) g[v].push_back({u,id});
    }
    // degree check
    for(int v=0;v<cid;++v){
        if(g[v].size()%8){ cout<<-1<<"\n"; return 0; }
    }

    /* ---------- step 5: first Euler (black/white) ---------- */
    vector<char> used(m,0), clr(m,0);          // 0 white,1 black later split
    vector<int> it(V,0), stV;
    stV.push_back(DUMMY);
    vector<int> order;
    vector<int> edgeStack;
    while(!stV.empty()){
        int v=stV.back();
        while(it[v]<(int)g[v].size() && used[g[v][it[v]].id]) ++it[v];
        if(it[v]==(int)g[v].size()){           // back-track
            if(edgeStack.size()){
                order.push_back(edgeStack.back());
                edgeStack.pop_back();
            }
            stV.pop_back();
        }else{
            auto e = g[v][it[v]++];
            used[e.id]=1;
            stV.push_back(e.to);
            edgeStack.push_back(e.id);
        }
    }
    for(int i=0;i<(int)order.size();++i)
        clr[order[i]] = (i&1);                 // 0 white,1 black

    /* ---------- step 6: second layer (white ⇒ 1/2, black ⇒ 3/4) ---------- */
    auto refine=[&](int base){
        fill(used.begin(),used.end(),0);
        fill(it.begin(),it.end(),0);
        for(int eid=0;eid<m;++eid) if(clr[eid]==base){
            if(used[eid]) continue;
            stV.clear(); edgeStack.clear(); order.clear();
            stV.push_back(einfo[eid].u);
            while(!stV.empty()){
                int v=stV.back();
                while(it[v]<(int)g[v].size() &&
                      ( used[g[v][it[v]].id] || clr[g[v][it[v]].id]!=base))
                    ++it[v];
                if(it[v]==(int)g[v].size()){
                    if(edgeStack.size()){
                        order.push_back(edgeStack.back());
                        edgeStack.pop_back();
                    }
                    stV.pop_back();
                }else{
                    auto e=g[v][it[v]++];
                    used[e.id]=1;
                    stV.push_back(e.to);
                    edgeStack.push_back(e.id);
                }
            }
            for(int i=0;i<(int)order.size();++i)
                clr[order[i]] = base*2 + (i&1) + 1; // 1/2 or 3/4
        }
    };
    refine(0); // white → 1/2
    refine(1); // black → 3/4

    /* ---------- step 7: output colours of obstacles ---------- */
    for(int i=0;i<n;++i){
        int c = clr[i];
        cout<<c<<(i+1==n?'\n':' ');
    }
    return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70