QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#326585 | #7699. Pearls | VeryAmazed | AC ✓ | 4231ms | 3908kb | C++14 | 5.5kb | 2024-02-13 14:50:30 | 2024-02-13 14:50:30 |
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;
vector<string> good_strings;
bool is_corner(vector<pii>& vec, int cur);
bool check(vector<pii>& vec, int curr);
bool works(vector<pii>& vec);
void go_next(int r1, int c1, vector<pii>& vec, vector<char>& path, vector<vector<bool>>& visited, int& ind, int dir);
void 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--;
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;
gen_path(r, c, vec, path, visited, ind, i);
}
sort(good_strings.begin(), good_strings.end());
if(good_strings.size() == 0){
cout << "impossible" << endl;
}else{
for(auto c : good_strings[0]){
cout << c;
}
cout << endl;
}
//cout << ss.str();
return 0;
}
void 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){
if(works(vec)){
string temp;
for(int i = 1; i < path.size(); i++){
temp.pb(path[i]);
}
good_strings.pb(temp);
}
return;
}else{
//cout << "stopped" << endl;
return;
}
}else if(ind >= 4){
if(!check(vec, ind-2)) return;
}
if(visited[r1][c1] || k - ind < abs(r-r1) + abs(c-c1)){
//cout << "stopped" << endl;
return;
}
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'){
go_next(r1, c1, vec, path, visited, ind, dir);
}else if(str[ind] == 'B'){
int dir1 = (dir+1)%4;
int dir2 = (dir-1+4)%4;
go_next(r1, c1, vec, path, visited, ind, dir1);
go_next(r1, c1, vec, path, visited, ind, dir2);
}else{
for(int i = 0; i < 4; i++){
go_next(r1, c1, vec, path, visited, ind, i);
}
}
visited[r1][c1] = false;
}
void 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++;
gen_path(r2, c2, vec, path, visited, ind, dir);
vec.pop_back();
path.pop_back();
ind--;
}
}
bool works(vector<pii>& vec){
/*
cout << "Works check" << endl;
for(auto p : vec){
cout << "(" << p.f << ", " << p.s << ") ";
}
cout << endl;
*/
for(int i =0; i < k; i++){
if(!check(vec, i)) return false;
}
return true;
}
bool check(vector<pii>& vec, int curr){
int prev = (curr-1 + k)%k;
int next = (curr+1)%k;
if(str[curr] == 'W'){
if(!(!is_corner(vec, curr) && (is_corner(vec, next) || is_corner(vec, prev)))){
//cout << "(" << vec[i].f << ", " << vec[i].s << ") " << endl;
return false;
}
}else if(str[curr] == 'B'){
if(!(is_corner(vec, curr) && !(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: 100
Accepted
time: 0ms
memory: 3648kb
input:
16 5 6 B.B.B.BW.WB..WB. 3 1
output:
EENNEESSSSWWWWNN
result:
ok single line: 'EENNEESSSSWWWWNN'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
6 5 5 W..B.B 3 3
output:
impossible
result:
ok single line: 'impossible'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
8 5 5 B.B.B.B. 5 5
output:
NNWWSSEE
result:
ok single line: 'NNWWSSEE'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
8 10 10 B.BWBWB. 2 10
output:
SSWWNNEE
result:
ok single line: 'SSWWNNEE'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
10 5 10 W.B.BW.B.B 4 4
output:
EENNWWWSSE
result:
ok single line: 'EENNWWWSSE'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
10 10 10 B.B.B.B.B. 7 3
output:
impossible
result:
ok single line: 'impossible'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
12 10 10 B.B.B.B.B.B. 10 1
output:
impossible
result:
ok single line: 'impossible'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
16 15 15 B.B.B.B.B.B.B.B. 4 4
output:
impossible
result:
ok single line: 'impossible'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
24 20 20 B.B.B.B.B.B.B.B.B.B.B.B. 1 8
output:
EESSEESSWWSSWWNNWWNNEENN
result:
ok single line: 'EESSEESSWWSSWWNNWWNNEENN'
Test #10:
score: 0
Accepted
time: 66ms
memory: 3600kb
input:
60 50 50 B.B.B.B.B.B.BWB.B.B.B..B.B.B.B.BWB.B.B.B.B.B.B.B.B.B.B.B.B.. 10 10
output:
impossible
result:
ok single line: 'impossible'
Test #11:
score: 0
Accepted
time: 103ms
memory: 3860kb
input:
60 50 50 WW.B.WBWB.BWB.B.B.B.B.B.B.B.B...B.B.B..B.B.B.B..B.B.B.B..B.B 38 20
output:
impossible
result:
ok single line: 'impossible'
Test #12:
score: 0
Accepted
time: 49ms
memory: 3628kb
input:
60 50 50 BWBWBWB.W..B.B..WWB.WB.BWB.B..B..B.B.B.B..B.B.B..B.B.B.B.B.. 5 13
output:
impossible
result:
ok single line: 'impossible'
Test #13:
score: 0
Accepted
time: 1300ms
memory: 3704kb
input:
60 50 50 B.W...W.W.B.B.WB.WB.B.B.B..B.B.B.B.B..B.B..B.B.BWWBW.B.WBWB. 31 21
output:
EEENNNNEEENNEEENNNEESSEESSSWWSSWWSSWWWSSWWWSSWWNNNWWWNNNEESS
result:
ok single line: 'EEENNNNEEENNEEENNNEESSEESSSWWSSWWSSWWWSSWWWSSWWNNNWWWNNNEESS'
Test #14:
score: 0
Accepted
time: 260ms
memory: 3756kb
input:
60 50 50 W.B.B..B.B.B....B.B.B.B.B..B.B.B.B..B.BWBWWB.B.WBWB..W.B.BWB 35 20
output:
EENNEEENNEENNNEENNWWNNWWSSSWWNNWWSSSWWSSEEESSWWWSSWWSSSEENNE
result:
ok single line: 'EENNEEENNEENNNEENNWWNNWWSSSWWNNWWSSSWWSSEEESSWWWSSWWSSSEENNE'
Test #15:
score: 0
Accepted
time: 289ms
memory: 3592kb
input:
60 50 50 W.B.BWB..WBWWBWB.BWB.B.B.B.B..B.B.B.B....B.B.B.B.B.B..BWB.BW 8 36
output:
impossible
result:
ok single line: 'impossible'
Test #16:
score: 0
Accepted
time: 704ms
memory: 3596kb
input:
60 50 50 BW.WB.BWB.B.B.B.B...B.B.B.B.B...B.B.B.B.B.B.B.B..B..B.B.BWBW 13 29
output:
impossible
result:
ok single line: 'impossible'
Test #17:
score: 0
Accepted
time: 337ms
memory: 3660kb
input:
60 50 50 B.B..B.B.B.B.B..WB.B.B.BW.W.BWB.BW.BWWB.B..B...B.B.B.B.B.B.. 16 35
output:
impossible
result:
ok single line: 'impossible'
Test #18:
score: 0
Accepted
time: 468ms
memory: 3908kb
input:
60 50 50 B.B...B..B..B..B..B.BW.WBWBWB..WBWBWB.B.B..B.B.B.B.B..B.B.B. 33 30
output:
impossible
result:
ok single line: 'impossible'
Test #19:
score: 0
Accepted
time: 2078ms
memory: 3660kb
input:
60 50 50 B...B.B.B..B.BWBWBWBWBWB.BWBWBW.WWB.B.B...B.B.B.B...B.B.B... 30 32
output:
impossible
result:
ok single line: 'impossible'
Test #20:
score: 0
Accepted
time: 345ms
memory: 3596kb
input:
60 50 50 WBWB.B.B.B...B.B..B..B...B.B.B.WBWB.WBWB...BWB..B.BWW.WB...B 33 12
output:
impossible
result:
ok single line: 'impossible'
Test #21:
score: 0
Accepted
time: 1007ms
memory: 3900kb
input:
60 50 50 BW.B.B.B.B...B.B...BWB.W.WWB.B...B..B.B...B.B..WBWB..WB.B.WW 15 14
output:
impossible
result:
ok single line: 'impossible'
Test #22:
score: 0
Accepted
time: 1629ms
memory: 3600kb
input:
60 50 50 B.BW.W.WWB....B..B..B.B.B...B...B.B.B.B.B.B.B..BWB.WB.BWB.WW 23 13
output:
impossible
result:
ok single line: 'impossible'
Test #23:
score: 0
Accepted
time: 4231ms
memory: 3860kb
input:
60 50 50 BWWBWBWWBWB.B.B..B.B....B....B...B.B...B..B.B.B.BW.B.BW.BWW. 15 38
output:
impossible
result:
ok single line: 'impossible'
Test #24:
score: 0
Accepted
time: 4229ms
memory: 3596kb
input:
60 50 50 BWWBWBWWBWB.B.B..B.B....B....B...B.B...B..B.B.B.BW.B.BW.BWWB 15 38
output:
impossible
result:
ok single line: 'impossible'
Test #25:
score: 0
Accepted
time: 825ms
memory: 3596kb
input:
60 50 50 W.BW.W.WWB....B..B..B.B.B...B...B.B.B.B.B.B.B..BWB.WB.BWB.WW 23 13
output:
impossible
result:
ok single line: 'impossible'
Test #26:
score: 0
Accepted
time: 3708ms
memory: 3596kb
input:
60 50 50 B.WB.B.BWBW.WB....B.B.B.B.B.B..B.B.B.B.B....B.B.B.B..WBWBWW. 28 5
output:
impossible
result:
ok single line: 'impossible'
Test #27:
score: 0
Accepted
time: 4055ms
memory: 3656kb
input:
60 50 50 B.B.WB..B...B..B.B.B...B.....B.B.B....BWWBW.BW.WBWBWB.W.BWB. 46 24
output:
impossible
result:
ok single line: 'impossible'
Test #28:
score: 0
Accepted
time: 2497ms
memory: 3600kb
input:
60 50 50 B.B.B.B...B.B..B.B.B..B.B.....BWB.WBWBWW.W..BWB.B...WW.BWB.. 18 23
output:
impossible
result:
ok single line: 'impossible'
Test #29:
score: 0
Accepted
time: 78ms
memory: 3628kb
input:
60 50 50 WW.B.BWWBWWBWBW.WB.B.B.B.B...B.B.B....B..B.B.B.B..B...B.B... 3 5
output:
impossible
result:
ok single line: 'impossible'
Test #30:
score: 0
Accepted
time: 163ms
memory: 3892kb
input:
60 50 50 WWB.B.B..BWB.BW.W..B.WB..BWB...B.B..B.B.B..B.B.B.B.B..B.B.B. 6 36
output:
impossible
result:
ok single line: 'impossible'