Submission #1068912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068912		Alebn	Naval battle (CEOI24_battle)	C++14	46 / 100	1333 ms	1048576 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct S {
    int x, y, d;
    S(){}
};
struct C {
    int i, j, time;
    string t;
    C(){}
    C(int timei, int ii, int ji, string ti):time(timei),i(ii),j(ji),t(ti){}
};
map<char,int> trans = {{'N',0}, {'E',1}, {'S',2}, {'W',3}};

void solve() {
    int n;
    char temp;
    cin >> n;
    vector<S> a(n);
    map<int,vector<int>> diagx, diagy, hori, verti;
    for(int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y >> temp;
        a[i].d = trans[temp];
        diagx[a[i].x + a[i].y].push_back(i);
        diagy[(max(a[i].x, a[i].y) - min(a[i].x, a[i].y)) * (a[i].x > a[i].y ? 1 : -1)].push_back(i);
        hori[a[i].y].push_back(i);
        verti[a[i].x].push_back(i);
    }
    // ADD COLLISION TIME
    vector<C> cols;
    // process diagx
    for(auto i : diagx) {
        sort(i.second.begin(), i.second.end(), [&](int x, int y){
            return a[x].y > a[y].y;
        });
        vector<int> st1, st0;
        for(int j = 0; j < i.second.size(); j++) {
            switch(a[i.second[j]].d) {
                case 0:
                    st0.push_back(i.second[j]);
                    break;
                case 1:
                    st1.push_back(i.second[j]);
                    break;
                case 2:
                    for(auto k : st1) cols.push_back(C(abs(a[k].x - a[i.second[j]].x), k, i.second[j], "diagx"));
                    break;
                case 3:
                    for(auto k : st0) cols.push_back(C(abs(a[k].x - a[i.second[j]].x), k, i.second[j], "diagx"));
                    break;
            }
        }
    }
    // process diagy
    for(auto i : diagy) {
        sort(i.second.begin(), i.second.end(), [&](int x, int y){
            return a[x].y < a[y].y;
        });
        vector<int> st1, st2;
        for(int j = 0; j < i.second.size(); j++) {
            switch(a[i.second[j]].d) {
                case 2:
                    st1.push_back(i.second[j]);
                    break;
                case 1:
                    st2.push_back(i.second[j]);
                    break;
                case 3:
                    for(auto k : st1) cols.push_back(C(abs(a[k].x - a[i.second[j]].x), k, i.second[j], "diagy"));
                    break;
                case 0:
                    for(auto k : st2) cols.push_back(C(abs(a[k].x - a[i.second[j]].x), k, i.second[j], "diagy"));
                    break;
            }
        }
    }
    // process hori
    for(auto i : hori) {
        sort(i.second.begin(), i.second.end(), [&](int x, int y){
            return a[x].x < a[y].x;
        });
        vector<int> st;
        for(int j = 0; j < i.second.size(); j++) {
            switch(a[i.second[j]].d) {
                case 1:
                    st.push_back(i.second[j]);
                    break;
                case 3:
                    for(auto k : st) cols.push_back(C(abs(a[k].x - a[i.second[j]].x) / 2, k, i.second[j], "hori"));
                    break;
            }
        }
    }
    // process verti
    for(auto i : verti) {
        sort(i.second.begin(), i.second.end(), [&](int x, int y){
            return a[x].y < a[y].y;
        });
        vector<int> st;
        for(int j = 0; j < i.second.size(); j++) {
            switch(a[i.second[j]].d) {
                case 2:
                    st.push_back(i.second[j]);
                    break;
                case 0:
                    for(auto k : st) cols.push_back(C(abs(a[k].y - a[i.second[j]].y) / 2, k, i.second[j], "verti"));
                    break;
            }
        }
    }
    sort(cols.begin(), cols.end(), [&](C x, C y){
        return x.time < y.time;
    });
    vector<int> diedat(n, -1);
    int cnt = 0;
    for(int i = 0; i < cols.size(); i++) {
        cnt = max(cnt, cols[i].time);
        //if(cols[i].i == 3 || cols[i].j == 3 || cols[i].i == 58 || cols[i].j == 58) cout << cols[i].i << " " << cols[i].j << " " << cols[i].time << " " << cols[i].t << "\n";
        if((diedat[cols[i].i] == -1 || diedat[cols[i].i] == cnt) && (diedat[cols[i].j] == -1 || diedat[cols[i].j] == cnt)) {
            diedat[cols[i].i] = cnt;
            diedat[cols[i].j] = cnt;
        }
    }
    for(int i = 0; i < n; i++) {
        if(diedat[i] == -1) cout << i + 1 << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Compilation message (stderr)

Main.cpp: In constructor 'C::C(long long int, long long int, long long int, std::string)':
Main.cpp:11:15: warning: 'C::time' will be initialized after [-Wreorder]
   11 |     int i, j, time;
      |               ^~~~
Main.cpp:11:9: warning:   'long long int C::i' [-Wreorder]
   11 |     int i, j, time;
      |         ^
Main.cpp:14:5: warning:   when initialized here [-Wreorder]
   14 |     C(int timei, int ii, int ji, string ti):time(timei),i(ii),j(ji),t(ti){}
      |     ^
Main.cpp: In function 'void solve()':
Main.cpp:40:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int j = 0; j < i.second.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~
Main.cpp:63:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 0; j < i.second.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~
Main.cpp:86:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int j = 0; j < i.second.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~
Main.cpp:103:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int j = 0; j < i.second.size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~
Main.cpp:119:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<C>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int i = 0; i < cols.size(); i++) {
      |                    ~~^~~~~~~~~~~~~

• 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: 0 / 30
• Subtask 7: 0 / 24