Submission #1108791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108791		8pete8	Naval battle (CEOI24_battle)	C++17	67 / 100	181 ms	32124 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 sub200(){
    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,realcrash;
    int mn=inf;
    for(int k=0;k<n;k++){
        mn=inf;
        realcrash.clear();
        for(int i=0;i<n;i++){
            if(dead[i])continue;
            crash.clear();
            int curmn=inf;
            for(int j=0;j<n;j++){
                if(dead[j])continue;
                int x=collides(i,j);
                if(x<curmn){
                    crash.clear();
                    crash.pb(j);
                    curmn=x;
                }
                else if(x!=inf&&x==curmn)crash.pb(j);
            }
            if(crash.size())crash.pb(i);
            if(curmn<mn)swap(crash,realcrash),mn=curmn;
        }
        for(auto i:realcrash)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<=200)sub200();
    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:13: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   70 | void sub200(){
      |             ^
Main.cpp:108:12: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  108 | void subSE(){
      |            ^
Main.cpp:126:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  126 | 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: 0 / 9
• Subtask 6: 30 / 30
• Subtask 7: 0 / 24