QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#326585#7699. PearlsVeryAmazedAC ✓4231ms3908kbC++145.5kb2024-02-13 14:50:302024-02-13 14:50:30

Judging History

你现在查看的是最新测评结果

  • [2024-02-13 14:50:30]
  • 评测
  • 测评结果:AC
  • 用时:4231ms
  • 内存:3908kb
  • [2024-02-13 14:50:30]
  • 提交

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'