Submission #1061386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061386		seoul_korea	Naval battle (CEOI24_battle)	C++17	46 / 100	1272 ms	1048576 KiB

Main

// Goten2308
#include<bits/stdc++.h>

using namespace std;
#define int long long
using ll = long long;
using ii = pair <int, int>;
#define fi first
#define se second 
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define BIT(x, y) ((x >> y) & 1)
#define MASK(x) (1 << x)
#define MOD 1000000007
#define MULTI_TEST1
#define __GOTEN_WILL_BE_BETTER__ signed main()
template <class T> bool maximize(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template <class T> bool minimize(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template <class T> void add(T& a, T b) { a += b; if(a >= MOD) a -= MOD; }
template <class T> void sub(T& a, T b) { a -= b; if(a < 0) a += MOD; }

const int maxN = (int)2e5 + 7;
map<ii, bool> isDelTime;
struct Event{
    int fr, to, at;
    Event() {
        fr = 0, to = 0, at = 0;
    }
    Event(int _fr, int _to, int _at) {
        fr = _fr;
        to = _to;
        at = _at;
    }
};

bool cmp(Event a, Event b) {
    return a.at < b.at;
}

struct Board{
    int x, y;
    char type;
} a[maxN];
vector<int> store[5];
int n;

int enc(char x) {
    if(x == 'S') return 0;
    if(x == 'N') return 1;
    if(x == 'E') return 2;
    if(x == 'W') return 3;
}

int calcTime(Board a, Board b) {
    if(enc(a.type) > enc(b.type)) swap(a, b);
    if(enc(a.type) == 0) {
        if(enc(b.type) == 1) {
            if(a.x > b.x || a.y != b.y || (a.x + b.x & 1)) return -1;
            return (a.x + b.x >> 1) - a.x;
        }
        if(enc(b.type) == 2) {
            if(b.x - a.x == a.y - b.y && a.y - b.y >= 0) return a.y - b.y;
            return -1;
        }
        if(enc(b.type) == 3) {
            if(b.x - a.x == b.y - a.y && b.y - a.y >= 0) return b.y - a.y;
            return -1;
        }
    }
    if(enc(a.type) == 1) {
        if(enc(b.type) == 2) {
            if(a.x - b.x == a.y - b.y && a.y - b.y >= 0) return a.y - b.y;
            return -1;
        }
        if(enc(b.type) == 3) {
            if(a.x - b.x == b.y - a.y && b.y - a.y >= 0) return b.y - a.y;
            return -1;
        }
    }
    if(enc(a.type) == 2) {
        if(enc(b.type) == 3) {
            if((a.y + b.y & 1) || a.x != b.x || a.y > b.y) return -1;
            return (a.y + b.y >> 1) - a.y;
        }
    }
}

// pair<int, int> midPos(Event e) {
//     Board cur = a[e.fr], other = a[e.to];
//     if(enc(cur.type) > enc(other.type)) swap(cur, other);
//     if(enc(cur.type) == 0) {
//         if(enc(other.type) == 1) {
//             return make_pair(cur.x + other.x >> 1, cur.y);
//         }
//         if(enc(other.type) == 2) {
//             return make_pair(other.x, cur.y);
//         }
//         if(enc(other.type) == 3) {
//             return make_pair(other.x, cur.y);
//         }
//     }
//     if(enc(cur.type) == 1) {
//         if(enc(other.type) == 2) {
//             return make_pair(other.x, cur.y);

//         }
//         if(enc(other.type) == 3) {
//             return make_pair(other.x, cur.y);
//         }
//     }
//     if(enc(cur.type) == 2) {
//         if(enc(other.type) == 3) {
//             return make_pair(cur.x, cur.y + other.y >> 1);
//         }
//     }
// }

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].y >> a[i].x >> a[i].type;
        store[enc(a[i].type)].pb(i);
    }
    vector<Event> timeline;
    for(int i = 1; i <= n; i++) {
        for(int nxt = 0; nxt <= 3; nxt++) {
            if(nxt == enc(a[i].type)) continue;
            for(auto j : store[nxt]) {
                if(i > j) continue;
                int k = calcTime(a[i], a[j]);
                if(k == -1) continue;
                timeline.push_back(Event(i, j, k));
            }
        }
    }
    sort(all(timeline), cmp);
    vector<bool> isAlive(n + 1, 1);
    Event last = Event();
    for(auto sukien : timeline) {
        if(isAlive[sukien.fr] && isAlive[sukien.to] || isDelTime.find(mp(sukien.fr, sukien.at)) != isDelTime.end() || isDelTime.find(mp(sukien.to, sukien.at)) != isDelTime.end()) {
            isAlive[sukien.fr] = 0;
            isAlive[sukien.to] = 0;
            // isDelTime[sukien.fr][sukien.at] = 1;
            isDelTime[mp(sukien.fr,sukien.at)] = 1;
            isDelTime[mp(sukien.to,sukien.at)] = 1;
        }
        // last = sukien;
        // cout << sukien.fr << ' ' << sukien.to << ' ' << sukien.at << endl;
    }
    for(int i = 1; i <= n; i++) if(isAlive[i]) cout << i << endl;
}

__GOTEN_WILL_BE_BETTER__ {
    #define task ""
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    if(fopen("task.inp", "r")){
        freopen("task.inp", "r", stdin);
        freopen("task.out", "w", stdout);
    }
    cin.tie(0)->ios_base::sync_with_stdio(0);
    int nTest = 1;
    #ifdef MULTI_TEST
    cin >> nTest;
    #endif
    while(nTest--) {
        solve();
    }
    cout << endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'long long int calcTime(Board, Board)':
Main.cpp:60:48: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   60 |             if(a.x > b.x || a.y != b.y || (a.x + b.x & 1)) return -1;
      |                                            ~~~~^~~~~
Main.cpp:61:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |             return (a.x + b.x >> 1) - a.x;
      |                     ~~~~^~~~~
Main.cpp:84:21: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   84 |             if((a.y + b.y & 1) || a.x != b.x || a.y > b.y) return -1;
      |                 ~~~~^~~~~
Main.cpp:85:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |             return (a.y + b.y >> 1) - a.y;
      |                     ~~~~^~~~~
Main.cpp: In function 'void solve()':
Main.cpp:142:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  142 |         if(isAlive[sukien.fr] && isAlive[sukien.to] || isDelTime.find(mp(sukien.fr, sukien.at)) != isDelTime.end() || isDelTime.find(mp(sukien.to, sukien.at)) != isDelTime.end()) {
      |            ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:140:11: warning: variable 'last' set but not used [-Wunused-but-set-variable]
  140 |     Event last = Event();
      |           ^~~~
Main.cpp: In function 'long long int enc(char)':
Main.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
   54 | }
      | ^
Main.cpp: In function 'long long int calcTime(Board, Board)':
Main.cpp:88:1: warning: control reaches end of non-void function [-Wreturn-type]
   88 | }
      | ^
Main.cpp: In function 'int main()':
Main.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:162:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:163:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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