Submission

[-SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS]

Score: 0

User: Newtonabc

Problemset: Optimal Placement

Language: cpp

Time: 0.002 second

Submitted On: 2025-03-01 23:21:42

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
struct point{
    int x,y;                                                                                                                                                                         
}arr[N];
int dist(point a,point b){
    return abs(a.x-b.x)+abs(a.y-b.y);
}
int m;
int low(int u){if(u>m) return u-m; return u;}
int up(int u){if(u<=m) return u+m; return u;}
int pick[N],ck[N];
vector<pair<int,pair<int,int>>> edge;
//weight u v
int main(){
    int n;
    cin>>n >>m;
    for(int i=1;i<=m;i++){
        point a,b;
        cin>>a.x >>a.y >>b.x >>b.y;
        arr[i]=a,arr[i+m]=b;
    }
    for(int i=1;i<=2*m;i++){
        for(int j=i+1;j<=2*m;j++){
            if(low(i)==low(j)) continue;
            int w=dist(arr[i],arr[j]);
            edge.push_back({w,{i,j}});
        }
    }
    int ans;
    for(int i=0;i<edge.size();i++){
        int w=edge[i].first;
        int u=edge[i].second.first;
        int v=edge[i].second.second;
        ans=w;
        /*cout<<w <<" " <<u <<" " <<v <<"\n";
        for(int i=1;i<=m;i++){
            cout<<pick[i] <<" ";
        }
        cout<<"\n";*/
        ck[u]=ck[v]=true;
        if((ck[low(u)] && ck[up(u)]) || (ck[low(v)] && ck[up(v)])) break;
        if(u>m) pick[u-m]=2;
        else pick[u]=1;
        if(v>m) pick[v-m]=2;
        else pick[v]=1;
    }
    cout<<ans <<"\n";
    for(int i=1;i<=m;i++){
        if(pick[i]==2) cout<<"B";
        else cout<<"A";
    }
}