제출 #1246773

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

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int DIR = 4;          // 0=E 1=S 2=W 3=N
int refl[2][DIR] = { {3,2,1,0}, {1,0,3,2} };            // '/' , '\'
int opp(int d){ return d^2; }

struct Ob{ int x,y; char t; };
struct Adj{ int to,id; };

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<Ob> a(n);
    for(auto &o:a) cin>>o.x>>o.y>>o.t;

    /* step A: nearest neighbours E,W,N,S */
    vector<array<int,DIR>> nxt(n);  const int NIL=-1;
    unordered_map<ll, vector<pair<int,int>>> rows,cols; rows.reserve(n*2); cols.reserve(n*2);
    auto key=[&](int p){ return (ll)p+2000000001LL; };          // shift to avoid neg
    for(int i=0;i<n;++i){
        rows[key(a[i].y)].push_back({a[i].x,i});
        cols[key(a[i].x)].push_back({a[i].y,i});
    }
    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);
            nxt[id][0] = (k+1<(int)vec.size()?vec[k+1].second:NIL);
        }
    }
    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);
            nxt[id][1] = (k+1<(int)vec.size()?vec[k+1].second:NIL);
        }
    }

    /* step B: build functional graph of states */
    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<DIR;++d){
            int out=refl[tp][d];
            int j=nxt[i][out];
            if(j==NIL) continue;
            go[idx(i,d)] = idx(j, opp(out));
        }
    }

    /* step C: detect cycles */
    vector<int> color(S,0), cycId(S,-1);
    vector<int> cycLen;
    int cid=0; vector<int> st;
    bool fail=false;
    for(int v=0;v<S && !fail;++v) if(!color[v]){
        int x=v;
        while(x!=-1 && !color[x]){
            color[x]=1; st.push_back(x); x=go[x];
        }
        if(x!=-1 && color[x]==1){
            vector<int> cyc; int y;
            do{ y=st.back(); st.pop_back(); cyc.push_back(y);}while(y!=x);
            if(cyc.size()%8){ fail=true; break; }
            for(int s:cyc) cycId[s]=cid;
            cycLen.push_back(cyc.size()); ++cid;
        }
        while(!st.empty()){ color[st.back()]=2; st.pop_back(); }
    }
    if(fail){ cout<<-1<<"\n"; return 0; }

    const int DUMMY = cid; int V=cid+1;

    /* step D: build edge list */
    vector<vector<Adj>> g(V);
    struct Edge{ int u,v,obs; };
    vector<Edge> edges; edges.reserve(n);

    for(int i=0;i<n;++i){
        int idA=-1,idB=-1;
        if(a[i].t=='/'){
            int sa0=cycId[idx(i,0)], sa1=cycId[idx(i,3)];
            int sb0=cycId[idx(i,1)], sb1=cycId[idx(i,2)];
            idA = (sa0!=-1?sa0:sa1); idB = (sb0!=-1?sb0:sb1);
        }else{
            int sa0=cycId[idx(i,0)], sa1=cycId[idx(i,1)];
            int sb0=cycId[idx(i,2)], sb1=cycId[idx(i,3)];
            idA = (sa0!=-1?sa0:sa1); idB = (sb0!=-1?sb0:sb1);
        }
        if(idA==-1) idA=DUMMY;
        if(idB==-1) idB=DUMMY;
        edges.push_back({idA,idB,i});
        int eid=edges.size()-1;
        g[idA].push_back({idB,eid});
        g[idB].push_back({idA,eid});          // always add twice
    }

    /* step E: degree check */
    for(int v=0; v<cid; ++v)
        if(g[v].size()%8){ cout<<-1<<"\n"; return 0; }

    /* helper: generic Euler colouring */
    auto euler_colour=[&](const vector<char>& useMask, vector<int>& res, int baseCol){
        int m=edges.size();
        vector<char> used(m,0); vector<size_t> it(V,0);
        for(int start=0; start<V; ++start){
            if(start!=DUMMY && g[start].empty()) continue;
            if(it[start]==g[start].size()) continue;
            vector<int> vs, es;
            vs.push_back(start);
            while(!vs.empty()){
                int v=vs.back();
                while(it[v]<g[v].size() && (used[g[v][it[v]].id] || !useMask[g[v][it[v]].id])) ++it[v];
                if(it[v]==g[v].size()){
                    if(!es.empty()){
                        res[es.back()] = baseCol + (es.size()%2);
                        es.pop_back();
                    }
                    vs.pop_back();
                }else{
                    auto e=g[v][it[v]++]; used[e.id]=1;
                    vs.push_back(e.to); es.push_back(e.id);
                }
            }
        }
    };

    /* step F: three phases */
    int m=edges.size();
    vector<int> col(m,-1);
    vector<char> all(m,1);
    euler_colour(all,col,0);                 // first pass: 0/1
    vector<char> white(m,0), black(m,0);
    for(int i=0;i<m;++i) (col[i]==0?white:black)[i]=1;
    euler_colour(white,col,1);               // 1/2
    euler_colour(black,col,3);               // 3/4

    /* step G: output */
    for(int i=0;i<m;++i) if(col[i]<1||col[i]>4){ cout<<-1<<"\n"; return 0; }
    vector<int> ans(n);
    for(int i=0;i<m;++i) ans[edges[i].obs]=col[i];
    for(int i=0;i<n;++i) cout<<ans[i]<<(i+1==n?'\n':' ');
    return 0;
}

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