Submission #1247317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247317		vht2025	Fliper (COCI22_fliper)	C++20	0 / 110	156 ms	73872 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; }

/* ------------ input ------------ */
struct Ob{ ll x,y,u,v; char c; };
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].c;
        a[i].u=a[i].x+a[i].y;
        a[i].v=a[i].x-a[i].y;
    }

    /* ------------ build neighbours on rotated grid ------------ */
    const int NIL=-1;
    vector<array<int,DIR>> nxt(n);            // next obstacle id or -1
    unordered_map<ll, vector<pair<ll,int>>> onU,onV;
    onU.reserve(n*2); onV.reserve(n*2);
    for(int i=0;i<n;++i){
        if(a[i].c=='\\') onU[a[i].u].push_back({a[i].v,i});
        else             onV[a[i].v].push_back({a[i].u,i});
    }
    for(auto &kv:onU){
        auto &vec=kv.second; sort(vec.begin(),vec.end());
        for(size_t k=0;k<vec.size();++k){
            int id=vec[k].second;
            // moving along +v (South) sees larger v
            nxt[id][1] = (k+1<vec.size()? vec[k+1].second : NIL);
            // moving along -v (North) sees smaller v
            nxt[id][3] = (k? vec[k-1].second : NIL);
        }
    }
    for(auto &kv:onV){
        auto &vec=kv.second; sort(vec.begin(),vec.end());
        for(size_t k=0;k<vec.size();++k){
            int id=vec[k].second;
            // moving along +u (East) sees larger u
            nxt[id][0] = (k+1<vec.size()? vec[k+1].second : NIL);
            // moving along -u (West) sees smaller u
            nxt[id][2] = (k? vec[k-1].second : NIL);
        }
    }

    /* ------------ functional graph on 4 n 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].c=='\\');
        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));
        }
    }

    /* ------------ detect cycles ------------ */
    vector<int> col(S,0), cycId(S,-1); vector<int> cycLen; 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){
            vector<int> cyc; int y;
            do{ y=st.back(); st.pop_back(); cyc.push_back(y);}while(y!=x);
            if(cyc.size()%8){ bad=true; break; }
            for(int s:cyc) cycId[s]=cid;
            cycLen.push_back(cyc.size()); ++cid;
        }
        while(!st.empty()){ col[st.back()]=2; st.pop_back(); }
    }
    if(bad){ cout<<-1<<"\n"; return 0; }

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

    /* ------------ build cycle-graph (one edge / obstacle) ------------ */
    struct Edge{ int u,v,obs; };
    vector<vector<pair<int,int>>> g(V);       // to , edgeId
    vector<Edge> e; e.reserve(n);

    for(int i=0;i<n;++i){
        int f1=-1,f2=-1;                      // two faces
        if(a[i].c=='/'){                      // (E,N) vs (S,W)
            int cA = cycId[idx(i,0)]; if(cA==-1) cA=cycId[idx(i,3)];
            int cB = cycId[idx(i,1)]; if(cB==-1) cB=cycId[idx(i,2)];
            f1=cA; f2=cB;
        }else{                               // '\'  (E,S) vs (W,N)
            int cA = cycId[idx(i,0)]; if(cA==-1) cA=cycId[idx(i,1)];
            int cB = cycId[idx(i,2)]; if(cB==-1) cB=cycId[idx(i,3)];
            f1=cA; f2=cB;
        }
        if(f1==-1) f1=DUMMY;
        if(f2==-1) f2=DUMMY;
        e.push_back({f1,f2,i});
        int id=e.size()-1;
        g[f1].push_back({f2,id});
        g[f2].push_back({f1,id});            // cả self-loop nhân đôi
    }

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

    /* ------------ hai lần Euler tô 4 màu ------------ */
    int m=e.size();
    vector<int> colE(m,-1);                  // kết quả 1..4
    vector<char> used(m,0); vector<size_t> it(V,0);

    auto euler=[&](const vector<char>& mask, int base){
        fill(used.begin(),used.end(),0);
        for(int s=0;s<V;++s) if(it[s]<g[s].size() && mask[g[s][it[s]].second]){
            vector<int> stV{ s }, stE;
            while(!stV.empty()){
                int v=stV.back();
                while(it[v]<g[v].size() && (used[g[v][it[v]].second]||!mask[g[v][it[v]].second])) ++it[v];
                if(it[v]==g[v].size()){
                    if(!stE.empty()){
                        int id=stE.back(); stE.pop_back();
                        colE[id]=base + (stE.size()&1);
                    }
                    stV.pop_back();
                }else{
                    auto [to,id]=g[v][it[v]++];
                    used[id]=1; stV.push_back(to); stE.push_back(id);
                }
            }
        }
    };

    /* lần 1: đen/trắng (0/1 tạm) */
    vector<char> all(m,1); fill(it.begin(),it.end(),0);
    euler(all,0);                             // colE = 0/1
    vector<char> white(m,0), black(m,0);
    for(int i=0;i<m;++i) (colE[i]==0?white:black)[i]=1;
    fill(it.begin(),it.end(),0); euler(white,1);   // thành 1/2
    fill(it.begin(),it.end(),0); euler(black,3);   // thành 3/4

    /* ------------ xuất ------------ */
    vector<int> ans(n);
    for(int i=0;i<m;++i) ans[e[i].obs]=colE[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