제출 #1080726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1080726		oscar1f	Naval battle (CEOI24_battle)	C++17	100 / 100	1368 ms	179796 KiB

Main

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

struct intersect {
    int distParc,premBat,deuzBat;
    bool operator < (const intersect& autre) const {
        return distParc>autre.distParc;
    } 
};

const int MAX_BAT=200*1000+5,INFINI=1000*1000*1000+5;
int nbBat;
pair<int,int> coord[MAX_BAT];
int direc[MAX_BAT],dateInter[MAX_BAT];
set<int> listeVal[4];
unordered_map<int,int> reNum[4];
vector<pair<int,int>> corres; 
set<pair<int,int>> posBat[MAX_BAT][6];
priority_queue<intersect> possi;
vector<vector<bool>> pris={{false,true,true,false},
                           {true,false,false,true},
                           {false,true,false,true},
                           {false,false,true,true},
                           {true,true,false,false},
                           {true,false,true,false}};
vector<int> numHache={0,0,1,2,2,3};
vector<pair<int,int>> pente={{1,1},
                             {1,1},
                             {0,1},
                             {1,-1},
                             {1,-1},
                             {1,0}};
vector<pair<int,int>> combin={{1,0},
                              {1,0},
                              {1,0},
                              {1,0},
                              {1,0},
                              {0,1}};



int calcInter(int bat1,int bat2) {
    int dist=0;
    if (coord[bat1].first==coord[bat2].first) {
        dist=abs(coord[bat1].second-coord[bat2].second)/2;
    }
    else if (coord[bat1].second==coord[bat2].second) {
        dist=abs(coord[bat1].first-coord[bat2].first)/2;
    }
    else if (abs(coord[bat1].first-coord[bat2].first)==abs(coord[bat1].second-coord[bat2].second)) {
        dist=abs(coord[bat1].first-coord[bat2].first);
    }
    else {
        return INFINI;
    }
    if (coord[bat1].first+dist*corres[direc[bat1]].first==coord[bat2].first+dist*corres[direc[bat2]].first and
        coord[bat1].second+dist*corres[direc[bat1]].second==coord[bat2].second+dist*corres[direc[bat2]].second) {
        return dist;
    }
    return INFINI;
}

void init(int idSom,int idSens) {
    int taille=posBat[idSom][idSens].size();
    if (taille==0) {
        return;
    }
    auto it=posBat[idSom][idSens].begin();
    int bat1,bat2,dist;
    for (int i=0;i<taille-1;i++) {
        bat1=(*it).second;
        it++;
        bat2=(*it).second;
        dist=calcInter(bat1,bat2);
        if (dist!=INFINI) {
            possi.push({dist,bat1,bat2});
        } 
    }
}
 
void suppr(int idSom,int idSens,int batSup,int som) {
    //cout<<"?"<<idSom<<" "<<idSens<<" "<<batSup<<" "<<som<<endl;
    auto it=posBat[idSom][idSens].lower_bound({som,batSup});
    if (it==posBat[idSom][idSens].end() or (*it)!=make_pair(som,batSup)) {
        return;
    }
    //cout<<"?"<<idSom<<" "<<idSens<<" "<<batSup<<" "<<som<<endl;
    posBat[idSom][idSens].erase(it);
    it=posBat[idSom][idSens].lower_bound({som,batSup});
    if (it==posBat[idSom][idSens].end() or it==posBat[idSom][idSens].begin()) {
        return;
    }
    int bat1,bat2=(*it).second,dist;
    it--;
    bat1=(*it).second;
    dist=calcInter(bat1,bat2);
    //cout<<idSens<<" : "<<bat1<<" "<<bat2<<" "<<dist<<endl;
    if (dist!=INFINI) {
        possi.push({dist,bat1,bat2});
    } 
}
 
void maj(int batSup,int dist) {
    //cout<<"!"<<batSup<<" "<<dist<<endl;
    dateInter[batSup]=dist;
    for (int j=0;j<6;j++) {
        if (pris[j][direc[batSup]]) {
            suppr(reNum[numHache[j]][coord[batSup].first*pente[j].first+coord[batSup].second*pente[j].second],j,batSup,coord[batSup].first*combin[j].first+coord[batSup].second*combin[j].second);
        }
    }
} 
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    corres={{0,-1},{1,0},{0,1},{-1,0}};
    cin>>nbBat;
    char carac;
    for (int i=1;i<=nbBat;i++) {
        cin>>coord[i].first>>coord[i].second>>carac;
        if (carac=='N') {
            direc[i]=0;
        }
        if (carac=='E') {
            direc[i]=1;
        }
        if (carac=='S') {
            direc[i]=2;
        }
        if (carac=='W') {
            direc[i]=3;
        }
        listeVal[0].insert(coord[i].first+coord[i].second);
        listeVal[1].insert(coord[i].second);
        listeVal[2].insert(coord[i].first-coord[i].second);
        listeVal[3].insert(coord[i].first);
        dateInter[i]=INFINI;
    }
    int numDeCeType;
    for (int i=0;i<4;i++) {
        numDeCeType=0;
        for (int j:listeVal[i]) {
            reNum[i][j]=numDeCeType;
            numDeCeType++;
        }
    }
    for (int i=1;i<=nbBat;i++) {
        for (int j=0;j<6;j++) {
            if (pris[j][direc[i]]) {
                posBat[reNum[numHache[j]][coord[i].first*pente[j].first+coord[i].second*pente[j].second]][j].insert({coord[i].first*combin[j].first+coord[i].second*combin[j].second,i});
            }
        }
    }
    for (int i=0;i<nbBat;i++) {
        for (int j=0;j<6;j++) {
            init(i,j);
        }
    }
    int bat1,bat2,dist;
    while (!possi.empty()) {
        dist=possi.top().distParc;
        bat1=possi.top().premBat;
        bat2=possi.top().deuzBat;
        //cout<<bat1<<" "<<bat2<<" "<<dist<<endl;
        possi.pop();
        if (dateInter[bat1]>=dist and dateInter[bat2]>=dist) {
            maj(bat1,dist);
            maj(bat2,dist);
        }
    }
    for (int i=1;i<=nbBat;i++) {
        if (dateInter[i]==INFINI) {
            cout<<i<<"\n";
        }
    }
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 11 / 11
• Subtask 5: 9 / 9
• Subtask 6: 30 / 30
• Subtask 7: 24 / 24