Submission #1254691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254691		glupan	Naval battle (CEOI24_battle)	C++20	76 / 100	445 ms	229320 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MAX_N = 1e5 + 5;

void solve() {
    int n; cin >> n;
    int x[n],y[n];
    char d[n];
    for(int i=0; i<n; i++) {
        cin >> x[i] >> y[i] >> d[i];
    }
    if(n <= 5000) {
        vector<vector<ll>> sudar(n+1, vector<ll>(n+1, 1e18));
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(d[i] == d[j]) {
                    continue;
                }
                if(d[i] == 'S') {
                    if(d[j] == 'N') {
                        if(x[i] == x[j] and y[i] < y[j]) {
                            sudar[i][j] = (y[j]-y[i]) / 2;
                        }
                    } else if(d[j] == 'E') {
                        if(x[i] + y[i] == x[j] + y[j] and y[i] < y[j]) {
                            sudar[i][j] = y[j] - y[i];
                        }
                    } else if(d[j] == 'W') {
                        if(x[i] - y[i] == x[j] - y[j] and y[i] < y[j]) {
                            sudar[i][j] = y[j] - y[i];
                        }
                    }
                }
                else if(d[i] == 'N') {
                    if(d[j] == 'E') {
                        if(x[i] - y[i] == x[j] - y[j] and y[i] > y[j]) {
                            sudar[i][j] = y[i] - y[j];
                        }
                    } else if(d[j] == 'W') {
                        if(x[i] + y[i] == x[j] + y[j] and y[i] > y[j]) {
                            sudar[i][j] = y[i] - y[j];
                        }
                    }
                }
                else if(d[i] == 'E') {
                    if(d[j] == 'W') {
                        if(y[i] == y[j] and x[i] < x[j]) {
                            sudar[i][j] = (x[j]-x[i]) / 2;
                        }
                    }
                }
            }
        }
        vector<pair<ll,pair<int,int>>>v;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(sudar[i][j] != 1e18) {
                    v.push_back({sudar[i][j], {i,j}});
                }
            }
        }
        sort(v.begin(), v.end());
        vector<int>blown(n+1,0);
        for(auto x : v) {
            //cout << x.first << " " << x.second.first << " " << x.second.second << endl;
            if(blown[x.second.first] > 0 and blown[x.second.first] != x.first or blown[x.second.second] > 0 and blown[x.second.second] != x.first) continue;
            blown[x.second.first] = x.first;
            blown[x.second.second] = x.first;
        }
        for(int i=0; i<n; i++) {
            if(!blown[i]) cout << i+1 << endl;
        }
    } else {
        vector<int> ans;
        vector<vector<pair<int,int>>>v(n);
        map<ll, int> m;
        int tren=1;
        for(int i=0; i<n; i++) {
            ll sum = x[i] + y[i];
            if(!m[sum]) {
                m[sum] = tren;
                tren++;
            }
            v[m[sum]-1].push_back({y[i], i});
        }
        for(int i=0; i<tren; i++) {
            stack<int>s;
            sort(v[i].begin(),  v[i].end());
            for(auto x : v[i]) {
                if(d[x.second] == 'S') {
                    s.push(x.second);
                    continue;
                }
                if(s.empty()) ans.push_back(x.second);
                else s.pop();
            }
            while(!s.empty()) {
                int cur = s.top();
                s.pop();
                ans.push_back(cur);
            }
        }
        for(auto x : ans) cout << x+1 << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int tc=1;
    while(tc--)
        solve();
}

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