Submission #1068723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068723		BigBadBully	Naval battle (CEOI24_battle)	C++17	0 / 100	2699 ms	1048576 KiB

Main

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
struct ship{
    int x,y;
    char dir;
    
    /*
    Northern — decreases the y coordinate by 1
    Southern — increases the y coordinate by 1
    Eastern — increases the x coordinate by 1
    Western — decreases the x coordinate by 1
    */
};

int calc(ship a, ship b)
{
    
    if (a.dir == b.dir)
        return 0;    
    if (a.x == b.x)
    {
        if (a.y < b.y)
            swap(a,b);
        if (a.dir == 'N' && b.dir == 'S')
            return (a.y-b.y)/2;
        return 0;    
    }
    if (a.y == b.y)
    {
        if (a.x < b.x)
            swap(a,b);
        if (a.dir == 'W' && b.dir == 'E')
            return (a.x-b.x)/2;
        return 0;
    }
    if (a.x + a.y == b.x + b.y)
    {
       if(a.dir == 'N')
       {
           if (b.dir == 'E')
           {
               if (b.x < a.x && a.y > b.y)
                return abs(a.x-b.x);
           }
           else if (b.dir == 'W')
           {
               if (b.x > a.x && a.y > b.y)
                return abs(a.x-b.x);
           }
       }
       else if (a.dir == 'S')
       {
           if (b.dir == 'E')
           {
                 if (b.x < a.x && a.y < b.y)
                return abs(a.x-b.x);
           }
           else if (b.dir == 'W')
           {
                 if (b.x > a.x  && a.y < b.y)
                return abs(a.x-b.x);
           }
       }
       else if (a.dir == 'W')
       {
           if (b.dir == 'N')
           {
               if (b.x < a.x && a.y < b.y)
                return abs(a.x-b.x);
           }
           else if (b.dir == 'S')
           {
               if (b.x < a.x && a.y > b.y)
                return abs(a.x-b.x);
           }
       }
       else if (a.dir == 'E')
       {
          if (b.dir == 'N')
           {
               if (b.x > a.x && a.y < b.y)
                return abs(a.x-b.x);
           }
           else if (b.dir == 'S')
           {
               if (b.x > a.x && a.y > b.y)
                return abs(a.x-b.x);
           }
       }
           
    }
    return 0;
}
signed main() {
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<ship> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i].x >> v[i].y;
        string s;
        cin >> s;
        v[i].dir = s[0];
    }
    set<int> left;
    for (int i = 0; i < n; i++)
        left.insert(i);
    vector<pair<int,pair<int,int>>> crash;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
            if (calc(v[i],v[j]))
                crash.push_back({calc(v[i],v[j]),{i,j}});
    sort(crash.begin(),crash.end());
    int i = 0;
    int old = 0;
    auto exset = left;
    while (old < crash.size())
    {
    
    while ((i == 0 || crash[i].ff == crash[i-1].ff) && i < crash.size())
        i++;
    
    for (old = old; old < i && old < crash.size(); old++)
    {
        int j = old;
        if (exset.find(crash[j].ss.ff) == exset.end() ||
        exset.find(crash[j].ss.ss) == exset.end())
            continue;
        if (left.find(crash[j].ss.ff) != left.end())
        left.erase(crash[j].ss.ff);
        if (left.find(crash[j].ss.ss) != left.end())
        left.erase(crash[j].ss.ss);
    }
  
    i++;
    
    exset = left;
    }
    if (left.size() > 0)
    for (int c : left)
        cout << c+1 << '\n';
        
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:122:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     while (old < crash.size())
      |            ~~~~^~~~~~~~~~~~~~
Main.cpp:125:58: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     while ((i == 0 || crash[i].ff == crash[i-1].ff) && i < crash.size())
      |                                                        ~~^~~~~~~~~~~~~~
Main.cpp:128:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (old = old; old < i && old < crash.size(); old++)
      |                                ~~~~^~~~~~~~~~~~~~

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