oj.uz

Submission #246959

# Submission time Handle Problem Language Result Execution time Memory
246959 2020-07-10T16:31:07 Z dorijanlendvaj Robots (APIO13_robots) C++14
100 / 100
 1206 ms 129336 KB 
//DUEL
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define shandom_ruffle(a, b) shuffle(a, b, rng)
#define vi vector<int>
#define vl vector<ll>
#define popcnt __builtin_popcount
#define popcntll __builtin_popcountll
#define all(a) begin(a),end(a)

using namespace std;
using namespace __gnu_pbds;

using ll=long long;
using ull=unsigned long long;
using ld=long double;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w,bool fl=false)
{
	cout<<w.size()<<en;
	for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
	if (w.size()) cout<<w[w.size()-1]<<en;
	if (fl) cout<<flush;
}

void M998()
{
	swap(MOD,MOD2);
}

ll raand()
{
	ll a=rund();
	a*=RAND_MAX;
	a+=rund();
    return a;
}

#define rand raand

ll raaand()
{
	return raand()*(MOD-7)+raand();
}

void compress(vi&v)
{
	set<int> s;
	for (auto a: v) s.insert(a);
	vi o(all(s));
	for (auto&a: v) a=lower_bound(all(o),a)-o.begin();
}

void compress(vl&v)
{
	set<ll> s;
	for (auto a: v) s.insert(a);
	vl o(all(s));
	for (auto&a: v) a=lower_bound(all(o),a)-o.begin();
}

string to_upper(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
	return a;
}

string to_lower(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
	return a;
}

ll sti(string a,int base=10)
{
	ll k=0;
	for (int i=0;i<(int)a.size();++i)
	{
		k*=base;
		k+=a[i]-'0';
	}
	return k;
}

template<class T>
void eras(vector<T>& a,T b)
{
	a.erase(find(a.begin(),a.end(),b));
}

string its(ll k,int base=10)
{
	if (k==0) return "0";
	string a;
	while (k)
	{
		a.push_back((k%base)+'0');
		k/=base;
	}
	reverse(a.begin(),a.end());
	return a;
}

ll min(ll a,int b)
{
	if (a<b) return a;
	return b;
}

ll min(int a,ll b)
{
	if (a<b) return a;
	return b;
}

ll max(ll a,int b)
{
	if (a>b) return a;
	return b;
}

ll max(int a,ll b)
{
	if (a>b) return a;
	return b;
}

ll gcd(ll a,ll b)
{
	if (b==0) return a;
	return gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
}

template<class T,class K>
pair<T,K> mp(T a,K b)
{
	return make_pair(a,b);
}

inline int mult(ll a,ll b)
{
	return (a*b)%MOD;
}

inline int pot(int n,int k)
{
	if (k==0) return 1;
	ll a=pot(n,k/2);
	a=mult(a,a);
	if (k%2) return mult(a,n);
	else return a;
}

int divide(int a,int b)
{
	return mult(a,pot(b,MOD-2));
}

inline int sub(int a,int b)
{
	if (a-b>=0) return a-b;
	return a-b+MOD;
}

inline int add(int a,int b)
{
	if (a+b>=MOD) return a+b-MOD;
	return a+b;
}

bool prime(ll a)
{
	if (a==1) return 0;
	for (int i=2;i<=round(sqrt(a));++i)
	{
		if (a%i==0) return 0;
	}
	return 1;
}

const int N=510;
int k,n,m;
string h[N];
int dis[10][10][N][N];
vector<pii> ch[N][N],im[N*N*9];
bool bio[N][N][4],bi[N][N];
pii re[N][N][4];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0}; //clockwise

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int i=0;i<10;++i) bases.push_back(rand()%(MOD-13893829*2)+13893829);
	cin>>k>>m>>n;
	for (int i=0;i<n;++i) cin>>h[i];
	for (int i=0;i<n;++i) for (int j=0;j<m;++j) for (int z=0;z<4;++z) if (!(bio[i][j][z] || h[i][j]=='x'))
	{
		int i1=i,j1=j,z1=z;
		pair<pii,int> pre;
		vector<pair<pii,int>> pro;
		while (1)
		{
			if (i1<0 || j1<0 || i1>=n || j1>=m || bio[i1][j1][z1] || h[i1][j1]=='x')
			{
				pii uf=pre.x;
				if (i1>=0 && j1>=0 && i1<n && j1<m && bio[i1][j1][z1]) uf=re[i1][j1][z1];
				//cout<<i<<' '<<j<<' '<<i1<<' '<<j1<<' '<<z<<' '<<uf.x<<' '<<uf.y<<en;
				for (auto a: pro)
				{
					if (uf!=mp(a.x.x,a.x.y)) ch[a.x.x][a.x.y].pb(uf);
					bio[a.x.x][a.x.y][a.y]=1;
					re[a.x.x][a.x.y][a.y]=uf;
				}
				break;
			}
			pre={{i1,j1},z1};
			pro.pb(pre);
			if (h[i1][j1]=='C') z1=(z1+1)%4;
			if (h[i1][j1]=='A') z1=(z1+3)%4;
			i1+=dx[z1];
			j1+=dy[z1];
		}
	}
	/*for (int i=0;i<n;++i) for (int j=0;j<m;++j)
	{
		cout<<i<<' '<<j<<':'<<en;
		for (auto a: ch[i][j]) cout<<a.x<<' '<<a.y<<en;
	}*/
	for (int i=0;i<n;++i) for (int j=0;j<m;++j) if (h[i][j]>='0' && h[i][j]<='9')
	{
		memset(bi,0,sizeof(bi));
		int z=h[i][j]-'0';
		queue<pair<pii,int>> q;
		q.push({{i,j},0});
		memset(dis[z][z],1,sizeof(dis[z][z]));
		while (q.size())
		{
			int i1=q.front().x.x,j1=q.front().x.y,d=q.front().y;
			q.pop();
			if (bi[i1][j1]) continue;
			bi[i1][j1]=1;
			dis[z][z][i1][j1]=d;
			for (auto a: ch[i1][j1]) q.push({a,d+1});
		}
	}
	for (int le=1;le<k;++le) for (int s=1;s<=k-le;++s)
	{
		int t=s+le;
		memset(dis[s][t],1,sizeof(dis[s][t]));
		for (int i=0;i<n;++i) for (int j=0;j<m;++j) for (int z=s;z<t;++z) dis[s][t][i][j]=min(dis[s][t][i][j],dis[s][z][i][j]+dis[z+1][t][i][j]);
		for (int i=0;i<k*n*m;++i) im[i].clear(),im[i].shrink_to_fit();
		memset(bi,0,sizeof(bi));
		for (int i=0;i<n;++i) for (int j=0;j<m;++j) if (dis[s][t][i][j]<k*n*m) im[dis[s][t][i][j]].eb(i,j);
		for (int di=0;di<k*n*m;++di)
		{
			for (auto a: im[di])
			{
				int i=a.x,j=a.y;
				if (bi[i][j]) continue;
				bi[i][j]=1;
				dis[s][t][i][j]=di;
				for (auto b: ch[i][j]) im[di+1].pb(b);
			}
		}
	}
	/*for (int s=1;s<=k;++s) for (int t=s;t<=k;++t)
	{
		cout<<s<<' '<<t<<en;
		for (int i=0;i<n;++i,cout<<en) for (int j=0;j<m;++j) cout<<dis[s][t][i][j]<<' ';
	}*/
	int mi=MOD;
	for (int i=0;i<n;++i) for (int j=0;j<m;++j) mi=min(mi,dis[1][k][i][j]);
	if (mi<k*n*m) cout<<mi<<en;
	else cout<<-1<<en;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 64760 KB Output is correct
2 Correct 40 ms 64768 KB Output is correct
3 Correct 43 ms 64760 KB Output is correct
4 Correct 40 ms 64768 KB Output is correct
5 Correct 40 ms 64760 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 64760 KB Output is correct
2 Correct 40 ms 64768 KB Output is correct
3 Correct 43 ms 64760 KB Output is correct
4 Correct 40 ms 64768 KB Output is correct
5 Correct 40 ms 64760 KB Output is correct
6 Correct 40 ms 64760 KB Output is correct
7 Correct 40 ms 64768 KB Output is correct
8 Correct 41 ms 64760 KB Output is correct
9 Correct 40 ms 64768 KB Output is correct
10 Correct 42 ms 64888 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 64760 KB Output is correct
2 Correct 40 ms 64768 KB Output is correct
3 Correct 43 ms 64760 KB Output is correct
4 Correct 40 ms 64768 KB Output is correct
5 Correct 40 ms 64760 KB Output is correct
6 Correct 40 ms 64760 KB Output is correct
7 Correct 40 ms 64768 KB Output is correct
8 Correct 41 ms 64760 KB Output is correct
9 Correct 40 ms 64768 KB Output is correct
10 Correct 42 ms 64888 KB Output is correct
11 Correct 346 ms 113628 KB Output is correct
12 Correct 62 ms 67960 KB Output is correct
13 Correct 167 ms 96484 KB Output is correct
14 Correct 466 ms 114644 KB Output is correct
15 Correct 308 ms 113536 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 64760 KB Output is correct
2 Correct 40 ms 64768 KB Output is correct
3 Correct 43 ms 64760 KB Output is correct
4 Correct 40 ms 64768 KB Output is correct
5 Correct 40 ms 64760 KB Output is correct
6 Correct 40 ms 64760 KB Output is correct
7 Correct 40 ms 64768 KB Output is correct
8 Correct 41 ms 64760 KB Output is correct
9 Correct 40 ms 64768 KB Output is correct
10 Correct 42 ms 64888 KB Output is correct
11 Correct 346 ms 113628 KB Output is correct
12 Correct 62 ms 67960 KB Output is correct
13 Correct 167 ms 96484 KB Output is correct
14 Correct 466 ms 114644 KB Output is correct
15 Correct 308 ms 113536 KB Output is correct
16 Correct 779 ms 129336 KB Output is correct
17 Correct 1206 ms 124444 KB Output is correct
18 Correct 736 ms 122012 KB Output is correct
19 Correct 711 ms 121080 KB Output is correct
20 Correct 1008 ms 122572 KB Output is correct