QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#326533 | #7699. Pearls | VeryAmazed | WA | 0ms | 3612kb | C++14 | 5.3kb | 2024-02-13 13:02:47 | 2024-02-13 13:02:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// if you end up using long double, you need to set the floating point notation to fixed, and set the percision to be very high
typedef long double ld;
// contrsuct umaps like this, unordered_map<long long, int, custom_hash> safe_map;
// FIXED_RANDOM is static so it doesn not get redeclared between function calls
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
#define INF 2001001001
#define INF2 2e18
#define MOD 1000000007
#define f0r(a, b) for (long long a = 0; a < b; a++)
#define f1r(a, b, c) for(long long a = b; a < c; a++)
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define pb push_back
#define pf push_front
#define f first
#define s second
#define mp make_pair
#define pll pair<ll, ll>
#define pii pair<int, int>
#define tp make_tuple
// first four are north, west, east ,south
int dir1[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dir2[] = {0, 1, 0, -1, 1, -1, 1, -1};
char dirc[] = {'S', 'E', 'N', 'W'};
int k, n, m;
int r, c;
string str;
bool is_corner(vector<pii>& vec, int cur);
bool works(vector<pii>& vec, vector<char>& path);
bool go_next(int r1, int c1, vector<pii>& vec, vector<char>& path, vector<vector<bool>>& visited, int& ind, int dir);
bool gen_path(int r1, int c1, vector<pii>& vec, vector<char>& path, vector<vector<bool>>& visited, int& ind, int dir);
int main() {
// apparently this does fast i/o
cin.tie(0) , ios::sync_with_stdio(0);
// use this if you read in from a file
/*
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
*/
stringstream ss;
// Do it once. Do it right.
// Read the problem statement carefully
// Plan out the steps in words on a piece of paper before implementing
// after RTE(obviously) but also WA, run valgrind!!!
//cout << fixed << setprecision(12);
// if you use ld, use the above and don't use string stream
// use instead of ceil(a, b) if a and b are positive
// (a + b - 1) / b
cin >> k >> n >> m;
cin >> str;
cin >> r >> c;
r--;
c--;
bool ok = false;
for(int i =0; i < 4; i++){
vector<pii> vec;
vector<char> path;
vec.pb({r, c});
path.pb(dirc[i]);
vector<vector<bool>> visited(n, vector<bool>(m, 0));
int ind = 0;
//cout << "dir: " << dirc[i] << "----------------------------" << endl;
if(gen_path(r, c, vec, path, visited, ind, i)){
for(int j = 1; j < path.size(); j++){
ss << path[j];
}
ss << endl;
ok = true;
break;
}
}
if(!ok){
ss << "impossible" << endl;
}
cout << ss.str();
return 0;
}
bool gen_path(int r1, int c1, vector<pii>& vec, vector<char>& path, vector<vector<bool>>& visited, int& ind, int dir){
if(ind == k){
if(r1 == r && c1 == c){
return works(vec, path);
}else{
//cout << "stopped" << endl;
return false;
}
}
if(visited[r1][c1] || k - ind < abs(r-r1) + abs(c-c1)){
cout << "stopped" << endl;
return false;
}
visited[r1][c1] = true;
/*
for(auto p : vec){
cout << "(" << p.f << ", " << p.s << ") ";
}
cout << endl;
for(auto c : path){
cout << c << " ";
}
cout << endl;
*/
if(str[ind] == 'W'){
if(go_next(r1, c1, vec, path, visited, ind, dir)) return true;
}else if(str[ind] == 'B'){
int dir1 = (dir+1)%4;
int dir2 = (dir-1+4)%4;
if(go_next(r1, c1, vec, path, visited, ind, dir1)) return true;
if(go_next(r1, c1, vec, path, visited, ind, dir2)) return true;
}else{
for(int i = 0; i < 4; i++){
if(go_next(r1, c1, vec, path, visited, ind, i)) return true;
}
}
visited[r1][c1] = false;
return false;
}
bool go_next(int r1, int c1, vector<pii>& vec, vector<char>& path, vector<vector<bool>>& visited, int& ind, int dir){
int r2, c2;
r2 = r1 + dir1[dir];
c2 = c1 + dir2[dir];
if((r2 >= 0 && r2 < n) && (c2 >= 0 && c2 < m)){
vec.pb(mp(r2, c2));
path.pb(dirc[dir]);
ind++;
if(gen_path(r2, c2, vec, path, visited, ind, dir)) return true;
vec.pop_back();
path.pop_back();
ind--;
}
return false;
}
bool works(vector<pii>& vec, vector<char>& path){
/*
cout << "Works check" << endl;
for(auto p : vec){
cout << "(" << p.f << ", " << p.s << ") ";
}
cout << endl;
*/
for(int i =0; i < k; i++){
int prev = (i-1 + k)%k;
int next = (i+1)%k;
if(str[i] == 'W'){
if(!(!is_corner(vec, i) && (is_corner(vec, next) || is_corner(vec, prev)))){
//cout << "(" << vec[i].f << ", " << vec[i].s << ") " << endl;
return false;
}
}else if(str[i] == 'B'){
if(!(is_corner(vec, i) && !(is_corner(vec, next) || is_corner(vec, prev)))){
//cout << is_corner(vec, i) << endl;
return false;
}
}
}
return true;
}
bool is_corner(vector<pii>& vec, int curr){
int prev = (curr-1 + k)%k;
int next = (curr+1)%k;
return (vec[prev].f != vec[next].f) && (vec[prev].s != vec[next].s);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3612kb
input:
16 5 6 B.B.B.BW.WB..WB. 3 1
output:
stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stopped stop...
result:
wrong answer 1st lines differ - expected: 'EENNEESSSSWWWWNN', found: 'stopped'