CSES - Datatähti Open 2019 - Results
Submission details
Task:Robot
Sender:pwild
Submission time:2019-01-20 00:30:24 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED32
#3ACCEPTED56
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1details
#2ACCEPTED0.01 s1details
#3ACCEPTED0.02 s1details
#4ACCEPTED0.01 s1details
#5ACCEPTED0.02 s1details
#6ACCEPTED0.02 s1details
#7ACCEPTED0.01 s1details
#8ACCEPTED0.01 s1details
#9ACCEPTED0.02 s2details
#10ACCEPTED0.01 s2details
#11ACCEPTED0.03 s2details
#12ACCEPTED0.01 s2details
#13ACCEPTED0.02 s2details
#14ACCEPTED0.02 s2details
#15ACCEPTED0.01 s2details
#16ACCEPTED0.01 s2details
#17ACCEPTED0.01 s2details
#18ACCEPTED0.03 s3details
#19ACCEPTED0.02 s3details
#20ACCEPTED0.02 s3details
#21ACCEPTED0.01 s3details
#22ACCEPTED0.02 s3details
#23ACCEPTED0.01 s3details
#24ACCEPTED0.02 s3details
#25ACCEPTED0.01 s3details
#26ACCEPTED0.03 s3details
#27ACCEPTED0.02 s3details
#28ACCEPTED0.01 s3details
#29ACCEPTED0.02 s3details
#30ACCEPTED0.01 s3details
#31ACCEPTED0.02 s3details
#32ACCEPTED0.02 s3details
#33ACCEPTED0.02 s3details
#34ACCEPTED0.01 s3details
#35ACCEPTED0.02 s3details
#36ACCEPTED0.02 s3details
#37ACCEPTED0.02 s3details
#38ACCEPTED0.01 s3details
#39ACCEPTED0.01 s3details

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define has(c,i) ((c).find(i) != end(c))
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

const ll di[] = {0,1,0,-1}, dj[] = {1,0,-1,0};

bool simulate(vvl a) {
	ll m = sz(a), n = sz(a[0]);
	vector<vb> mark(m,vb(n));

	ll i = 0, j = 0, dir = 0, cnt = 0;
	FOR(step,0,1000) {
		if (!mark[i][j]) {
			mark[i][j] = true;
			cnt++;
		}
		if (i == 0 && j == 0 && cnt == m*n) {
			cout << "success!" << endl;
			return true;
		}
		ll &prv = a[i][j];
		i += di[dir], j += dj[dir];
		if (i < 0 || i >= m || j < 0 || j >= n) {
			//cout << "out of bounds" << endl;
			return false;
		}
		if (a[i][j] != prv) dir = (dir+1)%4;
		prv = (prv+1)%3;
	}
	//cout << "no success" << endl;
	return false;
}

vvl construct(ll m, ll n, vl steps) {
	vvl a(m,vl(n,-1));
	
	vl cyc = {0,1,0,1,2,1,2,0,2};

	ll i = 0, j = 0;
	FOR(t,0,sz(steps)) {
		while (steps[t] --> 0) {
			if (a[i][j] == -1) a[i][j] = cyc[t%9];
			i += di[t%4], j += dj[t%4];
		}
	}

	return a;
}

void stuff() {
	vvl a = construct(4,6,{2,2,1,1,3,1,1,2,2,3,5,3});
	simulate(a);
}

vl steps(ll m, ll n) {
	if (m == 2 || n == 2) return {n-1,m-1,n-1,m-1};
	
	if (m < n) {
		vl res = steps(n,m);
		rotate(begin(res),begin(res)+(sz(res)-1),end(res));
		return res;
	}

	vl res = {3};
	FOR(i,0,(n-2)/4) {
		res.back()--;
		for (ll x: vl{m-2,1,m-3,3,m-3,1,m-2,4}) res.pb(x);
	}
	
	if (n%4 == 2) {
		res.back() -= 2;
		res.pb(m-1);
	} else {
		for (ll x: vl{m-4,2,m-5,1,m-3,1,1,2,2}) res.pb(x);
	}
	
	res.pb(n-1), res.pb(m-1);
	
	return res;
}



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	

	ll m, n; cin >> m >> n;
	
	if (m == 4 && n == 4) {
		cout << "IMPOSSIBLE" << endl;
	} else {
		vvl res = construct(m,n,steps(m,n));
		//simulate(res);
		FOR(i,0,m) {
			FOR(j,0,n) cout << "RGB"[res[i][j]];
			cout << endl;
		}
	}
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
2 2

correct output
RG
GR

user output
RG
GR

Test 2

Group: 1

Verdict: ACCEPTED

input
2 4

correct output
RRRG
GRRR

user output
RRRG
GRRR

Test 3

Group: 1

Verdict: ACCEPTED

input
2 6

correct output
RRRRRG
GRRRRR

user output
RRRRRG
GRRRRR

Test 4

Group: 1

Verdict: ACCEPTED

input
2 10

correct output
RRRRRRRRRG
GRRRRRRRRR

user output
RRRRRRRRRG
GRRRRRRRRR

Test 5

Group: 1

Verdict: ACCEPTED

input
2 50

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...
Truncated

Test 6

Group: 1

Verdict: ACCEPTED

input
2 80

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...
Truncated

Test 7

Group: 1

Verdict: ACCEPTED

input
2 98

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...
Truncated

Test 8

Group: 1

Verdict: ACCEPTED

input
2 100

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...
Truncated

Test 9

Group: 2

Verdict: ACCEPTED

input
2 2

correct output
RG
GR

user output
RG
GR

Test 10

Group: 2

Verdict: ACCEPTED

input
2 4

correct output
RRRG
GRRR

user output
RRRG
GRRR

Test 11

Group: 2

Verdict: ACCEPTED

input
2 6

correct output
RRRRRG
GRRRRR

user output
RRRRRG
GRRRRR

Test 12

Group: 2

Verdict: ACCEPTED

input
4 2

correct output
RG
GG
GG
GR

user output
RG
GG
GG
GR

Test 13

Group: 2

Verdict: ACCEPTED

input
4 4

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 14

Group: 2

Verdict: ACCEPTED

input
4 6

correct output
RRRRRG
GBGRGG
GGRBRG
GRRBRR

user output
RRRRRG
RBRBGG
RRBGBG
RGGGRR

Test 15

Group: 2

Verdict: ACCEPTED

input
6 2

correct output
RG
GG
GG
GG
GG
...

user output
RG
GG
GG
GG
GG
...

Test 16

Group: 2

Verdict: ACCEPTED

input
6 4

correct output
RRRG
RGBG
RRGG
BBGG
GRBG
...

user output
RRRG
RBGG
RGRR
RBGR
RRBR
...

Test 17

Group: 2

Verdict: ACCEPTED

input
6 6

correct output
RRRRRG
GBGRBG
GGGBBG
GGGBBG
GGRBRG
...

user output
RRGBBR
RBGBGR
RGGRGR
RGGRGR
RGRRBR
...

Test 18

Group: 3

Verdict: ACCEPTED

input
2 2

correct output
RG
GR

user output
RG
GR

Test 19

Group: 3

Verdict: ACCEPTED

input
2 4

correct output
RRRG
GRRR

user output
RRRG
GRRR

Test 20

Group: 3

Verdict: ACCEPTED

input
2 6

correct output
RRRRRG
GRRRRR

user output
RRRRRG
GRRRRR

Test 21

Group: 3

Verdict: ACCEPTED

input
4 2

correct output
RG
GG
GG
GR

user output
RG
GG
GG
GR

Test 22

Group: 3

Verdict: ACCEPTED

input
4 4

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 23

Group: 3

Verdict: ACCEPTED

input
4 6

correct output
RRRRRG
GBGRGG
GGRBRG
GRRBRR

user output
RRRRRG
RBRBGG
RRBGBG
RGGGRR

Test 24

Group: 3

Verdict: ACCEPTED

input
6 2

correct output
RG
GG
GG
GG
GG
...

user output
RG
GG
GG
GG
GG
...

Test 25

Group: 3

Verdict: ACCEPTED

input
6 4

correct output
RRRG
RGBG
RRGG
BBGG
GRBG
...

user output
RRRG
RBGG
RGRR
RBGR
RRBR
...

Test 26

Group: 3

Verdict: ACCEPTED

input
6 6

correct output
RRRRRG
GBGRBG
GGGBBG
GGGBBG
GGRBRG
...

user output
RRGBBR
RBGBGR
RGGRGR
RGGRGR
RGRRBR
...

Test 27

Group: 3

Verdict: ACCEPTED

input
2 100

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...
Truncated

Test 28

Group: 3

Verdict: ACCEPTED

input
4 20

correct output
RRRRRRRRRRRRRRRRRRRG
GBBBBBBBBBBBBBBBGRGG
GGRRRRRRRRRRRRRRRBRG
GRRRRRRRRRRRRRRRRBRR

user output
RRRRRRRRRRRRRRRRRRRG
RBRBBBBBBBBBBBBBBBGG
RRBGBBBBBBBBBBBBBBBG
RGGGRRRRRRRRRRRRRRRR

Test 29

Group: 3

Verdict: ACCEPTED

input
4 100

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...
Truncated

Test 30

Group: 3

Verdict: ACCEPTED

input
10 10

correct output
RRRRRRRRRG
GBGRBBGRBG
GGGBBGGBBG
GGGBBGGBBG
GGGBBGGBBG
...

user output
RRGBBBRRRB
GBGBGGRGBB
GGGRGRRBBB
GGGRGRRBBB
GGGRGRRBBB
...
Truncated

Test 31

Group: 3

Verdict: ACCEPTED

input
12 12

correct output
RRRRRRRRRRRG
RGBBGRBBGRBG
RRBGGBBGGBBG
RRBGGBBGGBBG
RRBGGBBGGBBG
...

user output
RRGBBBRRRRRB
RBGBGGRGBRGB
RGGRGRRBBGGB
RGGRGRRBBGGB
RGGRGRRBBGGB
...
Truncated

Test 32

Group: 3

Verdict: ACCEPTED

input
10 12

correct output
RRRRRRRRRRRG
RGBBGRBBGRBG
RRBGGBBGGBBG
RRBGGBBGGBBG
RRBGGBBGGBBG
...

user output
RRRRRRRRRRRG
GBBBBBBBBBGG
GGRRRRRRRRRR
GBBBBBBBBBGR
GRBBBBBBBBBR
...
Truncated

Test 33

Group: 3

Verdict: ACCEPTED

input
12 10

correct output
RRRRRRRRRG
GBGRBBGRBG
GGGBBGGBBG
GGGBBGGBBG
GGGBBGGBBG
...

user output
RRGBBBRRRB
GBGBGGRGBB
GGGRGRRBBB
GGGRGRRBBB
GGGRGRRBBB
...
Truncated

Test 34

Group: 3

Verdict: ACCEPTED

input
10 90

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...
Truncated

Test 35

Group: 3

Verdict: ACCEPTED

input
90 10

correct output
RRRRRRRRRG
GBGRBBGRBG
GGGBBGGBBG
GGGBBGGBBG
GGGBBGGBBG
...

user output
RRGBBBRRRB
GBGBGGRGBB
GGGRGRRBBB
GGGRGRRBBB
GGGRGRRBBB
...
Truncated

Test 36

Group: 3

Verdict: ACCEPTED

input
100 100

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
RRGBBBRRRRBBBBRGGGBBBBGGGGBRRR...
Truncated

Test 37

Group: 3

Verdict: ACCEPTED

input
98 100

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...
Truncated

Test 38

Group: 3

Verdict: ACCEPTED

input
100 98

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
RRGBBBRRRRBBBBRGGGBBBBGGGGBRRR...
Truncated

Test 39

Group: 3

Verdict: ACCEPTED

input
98 98

correct output
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR...

user output
RRGBBBRRRRBBBBRGGGBBBBGGGGBRRR...
Truncated