Submission #1103784

#TimeUsernameProblemLanguageResultExecution timeMemory
1103784TVSownNaval battle (CEOI24_battle)C++17
76 / 100
364 ms33600 KiB
///*** Sown_Vipro ***/// /// ->GIAI BA QUOC GIA<- /// #include<bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3") //#pragma GCC optimize ("unroll-loops") //#pragma GCC target("popcnt") #define F first #define S second #define pb push_back #define pi pair<int, int> #define pii pair<int, pair<int, int> > #define FOR(i, a, b) for(int i = a; i <= b; ++i) #define REP(i, a, b) for(int i = a; i >= b; --i) #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin); #define out(name) if(fopen(name, "w")) freopen(name, "w", stdout); #define szz(s) int(s.size()) const int N = 2e5 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7; int n; int d[N]; struct node{ int x, y, t, id; } p[N]; namespace sub1{ struct query{ int i, j, d; }; vector<query> q; pi Find(node a, node b){ int l = a.y, r = (a.t == 1 ? oo : 0); if(l > r) swap(l, r); // cout << l << " " << r << "\n"; if(l > b.y || b.y > r) return {-1, -1}; l = b.x, r = (b.t == 3 ? oo : 0); if(l > r) swap(l, r); // cout << l << " " << r << "\n"; if(l > a.x || a.x > r) return {-1, -1}; return {a.x, b.y}; } void check(node a, node b, int i, int j){ if(a.t == b.t){ if(a.x == b.x && a.y == b.y) q.pb({i, j, 0}); return; } if(a.t > b.t) swap(a, b); if(a.t == 1 && b.t == 2){ if(a.x == b.x && a.y <= b.y) q.pb({i, j, (b.y - a.y) / 2}); return; } if(a.t == 3 && b.t == 4){ // cout << a.x << " " << a.y << " " << b.x << " " << b.y << "\n"; if(a.y == b.y && a.x <= b.x) q.pb({i, j, (b.x - a.x) / 2}); return; } pi g = Find(a, b); if(g.F == -1) return; int x, y; if(b.t == 3){ x = g.F - b.x; } if(b.t == 4){ x = b.x - g.F; } if(a.t == 1){ y = g.S - a.y; } if(a.t == 2){ y = a.y - g.S; } // cout << g.F << " " << g.S << " " << b.x << " " << a.y << " " << x << " " << y << "\n"; if(x == y){ q.pb({i, j, x}); } } bool cmp(query a, query b){ return a.d < b.d; } void solve(){ FOR(i, 1, n){ FOR(j, 1, i - 1){ check(p[i], p[j], i, j); } } sort(q.begin(), q.end(), cmp); stack<pi> st; for(int i = 0; i < szz(q);){ int x = q[i].d; while(i < szz(q) && x == q[i].d){ // cout << q[i].i << " " << q[i].j << " " << x << " " << d[q[i].i] << " " << d[q[i].j] << "\n"; if(!d[q[i].i] && !d[q[i].j]){ st.push({q[i].i, q[i].j}); } ++i; } while(szz(st)){ d[st.top().F] = d[st.top().S] = 1; st.pop(); } } FOR(i, 1, n) if(!d[i]) cout << i << "\n"; } } namespace sub2{ vector<int> q[N]; vector<int> tmp; int f(int x){ return lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin(); } bool cmp(node a, node b){ if(a.x == b.x) return a.t > b.t; return a.x < b.x; } void solve(){ FOR(i, 1, n){ tmp.pb(p[i].x + p[i].y); p[i].id = i; } sort(tmp.begin(), tmp.end()); sort(p + 1, p + 1 + n, cmp); FOR(i, 1, n){ int F = f(p[i].x + p[i].y); if(p[i].t == 1){ if(q[F].size()){ d[p[i].id] = d[p[q[F].back()].id] = 1; q[F].pop_back(); } }else{ q[F].pb(i); } } FOR(i, 1, n) if(!d[i]) cout << i << "\n"; } } void solve(){ cin >> n; FOR(i, 1, n){ char t; cin >> p[i].x >> p[i].y >> t; if(t == 'S') p[i].t = 1; if(t == 'N') p[i].t = 2; if(t == 'E') p[i].t = 3; if(t == 'W') p[i].t = 4; } if(n <= 5000) sub1::solve(); else sub2::solve(); // sub2::solve(); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // inp("in.txt"); // out("out.txt"); int t = 1; // cin >> t; while(t--){ solve(); } }

Compilation message (stderr)

Main.cpp: In function 'void sub1::check(node, node, int, int)':
Main.cpp:78:9: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |         if(x == y){
      |         ^~
Main.cpp:79:17: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |             q.pb({i, j, x});
      |             ~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...