Submission #1108850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108850		8pete8	Naval battle (CEOI24_battle)	C++17	76 / 100	544 ms	103320 KiB

Main

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5+5,inf=1e18,minf=-1e18,lg=30;
//#undef int
int n,k,m;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
pii go[4]={{1,0},{0,1},{-1,0},{0,-1}};
int dead[mxn+10],direction[mxn+10];
pii v[mxn+10];
int collides(int x,int y){
    if(direction[x]==direction[y])return inf;
    if(direction[x]%2==direction[y]%2){
        if(direction[x]%2){
            if(v[x].f!=v[y].f)return inf;
            if(v[x].s>v[y].s)swap(x,y);
            if(direction[x]==1)return (v[y].s-v[x].s)/2;//going down (y+1)
            return inf;
        }
        else{
            if(v[x].s!=v[y].s)return inf;
            if(v[x].f>v[y].f)swap(x,y);
            if(direction[x]==0)return (v[y].f-v[x].f)/2;//going right (x+1)
            return inf;
        }
    }
    else{
        int diff=abs(v[x].f-v[y].f);
        pii nx={v[x].f+(diff*go[direction[x]].f),v[x].s+(diff*go[direction[x]].s)};
        pii ny={v[y].f+(diff*go[direction[y]].f),v[y].s+(diff*go[direction[y]].s)};
        if(nx==ny)return diff;
    }
    return inf;
}
void sub5000(){
    for(int i=0;i<n;i++){
        cin>>v[i].f>>v[i].s;
        char a;cin>>a;
        if(a=='E')direction[i]=0;
        if(a=='W')direction[i]=2;
        if(a=='N')direction[i]=3;
        if(a=='S')direction[i]=1;
    }
    //find first collision?
    //brute force
    vector<int>crash;
    int mn=inf;
    vector<pair<int,pii>>event;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int x=collides(i,j);
            if(x!=inf)event.pb({x,{i,j}});
        }
    }
    sort(all(event));
    int cur=0;
    for(int i=0;i<event.size();i++){
        crash.clear();
        while(event[cur].f==event[i].f){
            if(!dead[event[cur].s.f]&&!dead[event[cur].s.s]){
                crash.pb(event[cur].s.f);
                crash.pb(event[cur].s.s);
            }
            cur++;
        }
        for(auto i:crash)dead[i]=1;
    }
    for(int i=0;i<n;i++)if(!dead[i])cout<<i+1<<'\n';
}
void subSE(){
    map<int,vector<pair<pii,int>>>diag;
    for(int i=0;i<n;i++){
        cin>>v[i].f>>v[i].s;
        char a;cin>>a;
        if(a=='E')diag[v[i].f+v[i].s].pb({{v[i].f-v[i].s,i},0});
        else diag[v[i].f+v[i].s].pb({{v[i].f-v[i].s,i},1});
    }
    for(auto k:diag){
        sort(all(k.s));
        stack<int>st;
        for(auto i:k.s){
            if(i.s==0)st.push(i.f.s);
            else if(!st.empty())dead[i.f.s]=dead[st.top()]=1,st.pop();
        }
    }
    for(int i=0;i<n;i++)if(!dead[i])cout<<i+1<<'\n';
}
int32_t main(){
    fastio
    cin>>n;
    if(n<=5000)sub5000();
    else subSE();
}
/*
*/
/*
for ship moving on the same axis
we can just check if they are moving closer or not
if closer->a collision is gonna occur in dist(i,j)/2

ship not moving on the same axis
we can look at the node on a diagonal line
only ship on this line can collides with this ship
we can treat this line the same as the last case
but collision time will be dist(i,j) on the diagonal line instead
*/

Compilation message (stderr)

Main.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
Main.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void setIO(string name){
      |                       ^
Main.cpp:46:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   46 | int collides(int x,int y){
      |                         ^
Main.cpp:70:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   70 | void sub5000(){
      |              ^
Main.cpp: In function 'void sub5000()':
Main.cpp:92:18: 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]
   92 |     for(int i=0;i<event.size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp:82:9: warning: unused variable 'mn' [-Wunused-variable]
   82 |     int mn=inf;
      |         ^~
Main.cpp: At global scope:
Main.cpp:105:12: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  105 | void subSE(){
      |            ^
Main.cpp:123:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  123 | int32_t main(){
      |              ^
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".out").c_str(),"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: 30 / 30
• Subtask 7: 0 / 24