Submission #1048187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048187		adiyer	Robots (APIO13_robots)	C++17	0 / 100	1 ms	6492 KiB

robots

// #pragma optimize ("g",on)
// #pragma GCC optimize("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")

#include <bits/stdc++.h>

#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);
#define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0);
#define bitcount(n) __builtin_popcountll(n)
#define puts(x) (x ? "YES\n" : "NO\n");
#define ent (i == n ? '\n' : ' ')
#define all(x) x.begin(), x.end()
#define md ((l + r) >> 1)
#define rv(v) ((v << 1) | 1)
#define lv(v) (v << 1)
#define rs(v) rv(v), md + 1, r
#define ls(v) lv(v), l, md
#define len(s) (int) s.size()

#define pb push_back
#define S second
#define F first

// #define int long long

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector < ll > vll;
typedef pair < ll, ll > pll;
typedef vector < pair < ll, ll > > vpll;

const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int N = 5e2 + 23;
const int K = 2e5;
const int mod = 998244353;
const ll inf = 1e9 + 10;

//mt19937 rnd(07062006);

ll k, n, m, res, cur, cnt;	
ll d[10][N][N], ans[10][10], was[N][N][2][2][2][2];

char a[N][N];

bool good(ll x, ll y){
	return x >= 1 && y >= 1 && x <= n && y <= m && a[x][y] != 'x';
}

void move(ll &x, ll &y, ll d1, ll d2, ll d3, ll d4){
	ll X = x, Y = y;
	while(1){
		if(d1) x--;
		else if(d2) x++;
		else if(d3) y--;
		else y++;
		if(!good(x, y)) break;
		if(a[x][y] == 'C') swap(d1, d4), swap(d2, d3);
		if(a[x][y] == 'A') swap(d1, d3), swap(d2, d4);
	}
	if(d1) x++;
	else if(d2) x--;
	else if(d3) y++;
	else y--;
}

void bfs(pll s, ll id){
	ll x, y;
	queue < pll > q;
	for(ll i = 1; i <= n; i++)
		for(ll j = 1; j <= m; j++)
			d[id][i][j] = inf;
	q.push(s), d[id][s.F][s.S] = 0;
	while(len(q)){
		auto [X, Y] = q.front();
		q.pop();
		x = X, y = Y, move(x, y, 0, 0, 0, 1);
		if(good(x, y) && d[id][X][Y] + 1 < d[id][x][y]){
			d[id][x][y] = d[id][X][Y] + 1;
			q.push({x, y});
		}
		x = X, y = Y, move(x, y, 0, 0, 1, 0);
		if(good(x, y) && d[id][X][Y] + 1 < d[id][x][y]){
			d[id][x][y] = d[id][X][Y] + 1;
			q.push({x, y});
		}
		x = X, y = Y, move(x, y, 0, 1, 0, 0);
		if(good(x, y) && d[id][X][Y] + 1 < d[id][x][y]){
			d[id][x][y] = d[id][X][Y] + 1;
			q.push({x, y});
		}
		x = X, y = Y, move(x, y, 1, 0, 0, 0);
		if(good(x, y) && d[id][X][Y] + 1 < d[id][x][y]){
			d[id][x][y] = d[id][X][Y] + 1;
			q.push({x, y});
		}
	}
}

void output(){
	cin >> k >> n >> m, res = inf;
	for(ll i = 1; i <= n; i++)
		for(ll j = 1; j <= m; j++)
			cin >> a[i][j];
	for(ll i = 1; i <= n; i++)
		for(ll j = 1; j <= n; j++)
			if('1' <= a[i][j] && a[i][j] <= '9')
				bfs({i, j}, a[i][j] - '0');
	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= m; j++){
			for(ll id1 = k; id1 >= 1; id1--){
				for(ll id2 = id1; id2 <= k; id2++){
					if(id1 == id2){
						ans[id1][id2] = d[id1][i][j];
					}
					else{
						ans[id1][id2] = min(ans[id1 + 1][id2] + d[id1][i][j], ans[id1][id2 - 1] + d[id2][i][j]);
					}
				}
			}
			res = min(res, ans[1][k]), cur = 0;
		}
	}
	cout << res;
}

const bool cases = 0;

signed main(){
//  file("disrupt");
    adiyer();
    int tt = 1;
    if(cases) cin >> tt;
    for(int i = 1; i <= tt; i++){
    	output();
    }
}

Compilation message (stderr)

robots.cpp: In function 'void move(ll&, ll&, ll, ll, ll, ll)':
robots.cpp:56:5: warning: unused variable 'X' [-Wunused-variable]
   56 |  ll X = x, Y = y;
      |     ^
robots.cpp:56:12: warning: unused variable 'Y' [-Wunused-variable]
   56 |  ll X = x, Y = y;
      |            ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40