oj.uz

Submission #246957

# Submission time Handle Problem Language Result Execution time Memory
246957 2020-07-10T16:28:22 Z dorijanlendvaj Robots (APIO13_robots) C++14
60 / 100
 923 ms 163844 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();
		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 43 ms 64760 KB Output is correct
2 Correct 40 ms 64768 KB Output is correct
3 Correct 42 ms 64768 KB Output is correct
4 Correct 40 ms 64760 KB Output is correct
5 Correct 44 ms 64896 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 64760 KB Output is correct
2 Correct 40 ms 64768 KB Output is correct
3 Correct 42 ms 64768 KB Output is correct
4 Correct 40 ms 64760 KB Output is correct
5 Correct 44 ms 64896 KB Output is correct
6 Correct 41 ms 64768 KB Output is correct
7 Correct 41 ms 64768 KB Output is correct
8 Correct 41 ms 64768 KB Output is correct
9 Correct 44 ms 64768 KB Output is correct
10 Correct 43 ms 64888 KB Output is correct
11 Correct 299 ms 121812 KB Output is correct
12 Correct 57 ms 68088 KB Output is correct
13 Correct 158 ms 96760 KB Output is correct
14 Correct 384 ms 127224 KB Output is correct
15 Correct 281 ms 115060 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 64760 KB Output is correct
2 Correct 40 ms 64768 KB Output is correct
3 Correct 42 ms 64768 KB Output is correct
4 Correct 40 ms 64760 KB Output is correct
5 Correct 44 ms 64896 KB Output is correct
6 Correct 41 ms 64768 KB Output is correct
7 Correct 41 ms 64768 KB Output is correct
8 Correct 41 ms 64768 KB Output is correct
9 Correct 44 ms 64768 KB Output is correct
10 Correct 43 ms 64888 KB Output is correct
11 Correct 299 ms 121812 KB Output is correct
12 Correct 57 ms 68088 KB Output is correct
13 Correct 158 ms 96760 KB Output is correct
14 Correct 384 ms 127224 KB Output is correct
15 Correct 281 ms 115060 KB Output is correct
16 Correct 694 ms 129408 KB Output is correct
17 Runtime error 923 ms 163844 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -