Submission #1074890

#TimeUsernameProblemLanguageResultExecution timeMemory
1074890pawnedNaval battle (CEOI24_battle)C++17
30 / 100
421 ms32888 KiB
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back typedef long long ll; typedef pair<ll, ll> ii; typedef vector<ll> vi; const char nl = '\n'; void fastIO() { ios::sync_with_stdio(false); cin.tie(0); } map<char, int> conv = {{'S', 0}, {'N', 1}, {'E', 2}, {'W', 3}}; int main() { fastIO(); int N; cin>>N; vector<pair<int, ii>> ships; // {type, {x, y}} map<ll, vector<pair<ii, ii>>> alld; // all on diagonal x+y=i, going down // set of {{x, y}, {type, id}} for (int i = 0; i < N; i++) { ll x, y; char d; cin>>x>>y>>d; ships.pb({conv[d], {x, y}}); alld[x + y].pb({{x, y}, {conv[d], i}}); } /* cout<<"ships: "; for (pair<int, ii> p : ships) cout<<"("<<p.fi<<", "<<p.se.fi<<", "<<p.se.se<<"); "; cout<<endl;*/ vector<bool> alive(N, true); // still alive for (pair<ll, vector<pair<ii, ii>>> pr : alld) { // cout<<"at "<<pr.fi<<endl; sort(pr.se.begin(), pr.se.end()); int K = pr.se.size(); vector<char> dir; // A = east, B = south vi idx; for (int j = 0; j < K; j++) { if (pr.se[j].se.fi == 2) dir.pb('A'); else dir.pb('B'); idx.pb(pr.se[j].se.se); } /* cout<<"K: "<<K<<endl; cout<<"dir: "; for (char c : dir) cout<<c<<" "; cout<<endl; cout<<"idx: "; for (int x : idx) cout<<x<<" "; cout<<endl;*/ // remove all consec stack<int> q; // all existing A ids, most recent on top for (int j = 0; j < K; j++) { if (dir[j] == 'A') { q.push(idx[j]); } else { if (!q.empty()) { int x = q.top(); q.pop(); // cout<<"removed "<<x<<" "<<idx[j]<<endl; alive[x] = false; alive[idx[j]] = false; } } } } // cout<<"ANSWER: "<<endl; for (int i = 0; i < N; i++) { if (alive[i]) cout<<(i + 1)<<endl; } }
#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...