Submission

Score: 0

User: GastrointestinalTrackInflammation

Problemset: Optimal Placement

Language: cpp

Time: 0.012 second

Submitted On: 2026-10-05 16:19:37

#include<bits/stdc++.h>

using namespace std;

#define inall(x) for(auto& i:x)cin>>i;
#define outall(x) {for(auto i:x)cout<<i<<' ';cout<<endl;}
using ll = long long;
using df = double;

void dfs(int i, bool visited[], vector<int>adj[], stack<int>&st){
    for(auto x:adj[i]){
        if(visited[x])continue;
        visited[x]=1;
        dfs(x,visited,adj,st);
    }
    st.push(i);
}

vector<int>kosaraju(int n,vector<int>adj[],vector<int>revadj[]){
    vector<int>ans(n+1,0);
    bool visited[n+1]={0};
    bool visited2[n+1]={0};
    stack<int>st;
    stack<int>st2;
    for(int i=1;i<=n;i++){
        if(visited[i])continue;
        visited[i]=1;
        dfs(i,visited,adj,st);
    }
    while(!st.empty()){
        int i=st.top();
        st.pop();
        if(visited2[i])continue;
        visited2[i]=1;
        dfs(i,visited2,revadj,st2);
        while(!st2.empty()){
            int cur=st2.top();
            st2.pop();
            ans[cur]=i;
        }
    }
    return ans;
}

ll distant(pair<ll,ll>a,pair<ll,ll>b){
    return abs(a.first-b.first)+abs(a.second-b.second);
}

void solve(){
    int n;
    int m;
    cin>>n>>m;
    vector<int>ansvec(m+1);
    vector<pair<ll,ll>>a(m+1),b(m+1);
    for(int i=1;i<=m;i++){
        cin>>a[i].first>>a[i].second;
        cin>>b[i].first>>b[i].second;
    }
    ll l=0,r=2*n,mid;
    ll ans=0;
    while(l<=r){
        mid=l+(r-l)/2;
        vector<int>adj[2*m+1];
        vector<int>revadj[2*m+1];
        for(int i=1;i<=m;i++){
            for(int j=i+1;j<=m;j++){
                int ib=i+m,jb=j+m;
                if(distant(a[i],a[j])<mid){
                    adj[i].push_back(jb);
                    revadj[jb].push_back(i);
                    adj[j].push_back(ib);
                    revadj[ib].push_back(j);
                }
                if(distant(a[i],b[j])<mid){
                    adj[i].push_back(j);
                    revadj[j].push_back(i);
                    adj[jb].push_back(ib);
                    revadj[ib].push_back(jb);
                }
                if(distant(b[i],a[j])<mid){
                    adj[ib].push_back(jb);
                    revadj[jb].push_back(ib);
                    adj[j].push_back(i);
                    revadj[i].push_back(j);
                }
                if(distant(b[i],b[j])<mid){
                    adj[ib].push_back(j);
                    revadj[j].push_back(ib);
                    adj[jb].push_back(i);
                    revadj[i].push_back(jb);
                }
            }
        }
        vector<int>scc=kosaraju(m*2,adj,revadj);
        bool isgood=1;
        for(int i=1;i<=m;i++){
            if(scc[i]==scc[i+m]){
                isgood=0;
                break;
            }
        }
        if(!isgood){
            r=mid-1;
            continue;
        }
        ans=mid;    
        l=mid+1;
        int maxcom=0;
        for(auto x:scc)maxcom=max(maxcom,x);
        int indeg[maxcom+1]={0};
        int comorder[maxcom+1]={0};
        int curorder=0;
        vector<int>comadj[maxcom+1];
        queue<int>q;
        for(int i=1;i<=m;i++){
            for(auto j:adj[i]){
                if(scc[i]==scc[j])continue;
                indeg[scc[j]]++;
                comadj[scc[i]].push_back(scc[j]);
            }
        }
        for(int i=1;i<=maxcom;i++){
            if(indeg[i]==0)q.push(i);
        }
        while(!q.empty()){
            int cur=q.front();
            q.pop();
            comorder[cur]=curorder;
            curorder++;
            for(auto next:comadj[cur]){
                indeg[next]--;
                if(indeg[next]==0)q.push(next);
            }
        }
        for(int i=1;i<=m;i++){
            if(comorder[scc[i]]>comorder[scc[i+m]])ansvec[i]=0;//a;
            else ansvec[i]=1;//b
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=m;i++){
        if(ansvec[i]==0)cout<<'A';
        else cout<<'B';
    }
    cout<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--)solve();
    return 0;
}

/*
5 2
1 1 1 5
4 2 5 5
*/