Submission #553619

#TimeUsernameProblemLanguageResultExecution timeMemory
553619AwerarNautilus (BOI19_nautilus)C++14
100 / 100
215 ms704 KiB
#include <iostream> #include <vector> #include <string> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <limits.h> #include <math.h> #include <chrono> #include <queue> #include <stack> #include <bitset> #include <algorithm> using namespace std; #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #define ll long long #define vi vector<ll> #define vvi vector<vi> #define p2 pair<ll, ll> #define p3 tuple<ll,ll,ll> #define p4 vi #define ip3 tuple<int,int,int> #define ip4 tuple<int,int,int,int> #define vp2 vector<p2> #define vp3 vector<p3> #define inf 2e9 #define linf 1e17 #define read(a) cin >> a #define write(a) cout << (a) << "\n" #define dread(type, a) type a; cin >> a #define dread2(type, a, b) dread(type, a); dread(type, b) #define dread3(type, a, b, c) dread2(type, a, b); dread(type, c) #define dread4(type, a, b, c, d) dread3(type, a, b, c); dread(type, d) #define dread5(type, a, b, c, d, e) dread4(type, a, b, c, d); dread(type, e) #ifdef _DEBUG #define deb __debugbreak(); #else #define deb ; #endif #define rep(i, high) for (ll i = 0; i < high; i++) #define repp(i, low, high) for (ll i = low; i < high; i++) #define repe(i, container) for (auto& i : container) #define per(i, high) for (ll i = high; i >= 0; i--) #define readpush(type,vect) type temp; read(temp); vect.push_back(temp); #define readvector(type, name, size) vector<type> name(size); rep(i,size) {dread(type,temp); name[i]=temp;} #define readinsert(type,a) {type temp; read(temp); a.insert(temp);} #define all(a) begin(a),end(a) #define setcontains(set, x) (set.find(x) != set.end()) #define stringcontains(str, x) (str.find(x) != string::npos) #define within(a, b, c, d) (a >= 0 && a < b && c >= 0 && c < d) #define ceildiv(x,y) ((x + y - 1) / y) #define fract(a) (a-floor(a)) #define sign(a) ((a>0) ? 1 : -1) #define MW 500 auto Start = chrono::high_resolution_clock::now(); inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } ll w, h, m; vector<vector<bool>> grid; string instructions; int main() { //fast(); cin >> h >> w >> m; grid.resize(w, vector<bool>(h)); for(int y = 0; y < h; y++) { for(int x = 0; x < w; x++) { char c; cin >> c; grid[x][y] = c == '#'; } } cin >> instructions; vector<bitset<MW>> dp_state(h, bitset<500>()), free_pos(h, bitset<500>()); for(int y = 0; y < h; y++) { for(int x = 0; x < w; x++) { if(!grid[x][y]) free_pos[y].set(x, true); } dp_state[y] = free_pos[y]; } for(auto iter = instructions.begin(); iter != instructions.end(); iter++) { string dirs; dirs += *iter; if(dirs == "?") { dirs = "ENWS"; } vector<bitset<MW>> next_state(h, bitset<MW>()); for(char c : dirs) { for(int y = 0; y < h; y++) { switch (c) { case 'W': next_state[y] |= (dp_state[y] >> 1); break; case 'E': next_state[y] |= (dp_state[y] << 1); break; case 'N': if(y + 1 < h) next_state[y] |= dp_state[y + 1]; break; case 'S': if(y > 0) next_state[y] |= dp_state[y - 1]; break; } } } for(int y = 0; y < h; y++) { next_state[y] &= free_pos[y]; } dp_state = next_state; /*cout << "Instruction " << (*iter) << endl; for(int y = 0; y < h; y++) { for(int x = 0; x < w; x++) { cout << (dp_state[y][x] ? "o" : (grid[x][y] ? "#" : ".")); } cout << endl; }*/ } int ans = 0; for(int y = 0; y < h; y++) { ans += dp_state[y].count(); } write(ans); } /* 5 9 7 ...##.... ..#.##..# ..#....## .##...#.. ....#.... WS?EE?? */

Compilation message (stderr)

nautilus.cpp:19: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   19 | #pragma GCC optimization ("O3")
      | 
nautilus.cpp:20: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   20 | #pragma GCC optimization ("unroll-loops")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...