Submission #1311859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311859		HoriaHaivas	Naval battle (CEOI24_battle)	C++20	30 / 100	296 ms	51064 KiB

Main

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

struct nava
{
    int x;
    int y;
    char dir;
};

struct ceva
{
    int x;
    int y;
    int id;
};

bool cmp(ceva a, ceva b)
{
    return a.y<b.y;
}

nava ship[200005];
bool sunk[200005];
set<pair<int,int>> st[200005];
map<int,int> normie;
map<pair<int,int>,int> id;
vector<int> vals;
vector<ceva> v;

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,i,j,rez,when,cnt,diag,ide;
    cin >> n;
    for (i=1; i<=n; i++)
    {
        cin >> ship[i].x >> ship[i].y >> ship[i].dir;
        swap(ship[i].x,ship[i].y);
        id[ {ship[i].x,ship[i].y}]=i;
        vals.push_back(ship[i].x+ship[i].y);
    }
    sort(vals.begin(),vals.end());
    cnt=0;
    for (i=0; i<vals.size(); i++)
    {
        if (i==0 || vals[i]!=vals[i-1])
            cnt++;
        normie[vals[i]]=cnt;
    }
    for (i=1; i<=n; i++)
    {
        diag=normie[ship[i].x+ship[i].y];
        if (ship[i].dir=='E')
        st[diag].insert({ship[i].x,ship[i].y});
        if (ship[i].dir=='S')
            v.push_back({ship[i].x,ship[i].y,i});
    }
    sort(v.begin(),v.end(),cmp);
    for (auto x : v)
    {
        diag=normie[x.x+x.y];
        if (!st[diag].empty())
        {
            auto test=st[diag].upper_bound({x.x,x.y});
            if (test!=st[diag].end())
            {
                ide=id[{(*test).first,(*test).second}];
                sunk[x.id]=1;
                sunk[ide]=1;
                st[diag].erase(test);
            }
        }
    }
    for (i=1;i<=n;i++)
    {
         if (!sunk[i])
             cout << i << "\n";
    }
    return 0;
}

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