oj.uz

Submission #262838

# Submission time Handle Problem Language Result Execution time Memory
262838 2020-08-13T09:50:28 Z user202729 Robots (APIO13_robots) C++17
60 / 100
 1500 ms 85444 KB 
// 2
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>


int numRobot, numRow, numCol;
std::vector<std::vector<char>> data;
struct Pos{
	int row, col;
	int index() const{
		assert((unsigned) row<(unsigned) numRow); assert((unsigned) col<(unsigned) numCol);
		return col+numCol*row;
	}
};
struct State{
	int dir; // dir+1: clockwise
	int row, col;
	std::pair<int, int> dirVector() const{
		std::pair<int, int> result{1, 0};
		switch(dir){
			case 3: result={result.second,-result.first};
			case 2: result={result.second,-result.first};
			case 1: result={result.second,-result.first};
			case 0: return result;
		}
		assert(false);
	}

	int index() const{return dir+4*Pos{row, col}.index();}
};

int const loop=-2, uncomputed=-1;
std::vector<int> memory;

int compute(State it){
	auto& curMemory=memory[it.index()];
	if(curMemory!=uncomputed) return curMemory;

	State next=it;
	switch(data[next.row][next.col]){
		case 'A':
			next.dir=(next.dir-1)&3; break;
		case 'C':
			next.dir=(next.dir+1)&3; break;
		case 'x':
			assert(false); __builtin_unreachable();
	}
	next.row+=next.dirVector().first; next.col+=next.dirVector().second;

	if((unsigned)next.row>=(unsigned)numRow or (unsigned)next.col>=(unsigned)numCol or
			data[next.row][next.col]=='x')
		return curMemory=Pos{it.row, it.col}.index();

	curMemory=loop;
	return curMemory=compute(next);
}

int getMemory(int pos, int dir){
	int result=memory[dir+4*pos];
	assert(result!=uncomputed);
	return result;
}

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	std::cin>>numRobot>>numCol>>numRow;
	if(numRobot==1){std::cout<<"0\n"; return 0;}
	data.resize(numRow);
	for(auto& row: data){
		row.resize(numCol+1);
		std::cin>>row.data();
		assert(row.back()==0); row.pop_back();
		assert(row.back()!=0);
	}

	memory.assign(numRow*numCol*4, uncomputed);
	for(int row=0; row<numRow; ++row)
		for(int col=0; col<numCol; ++col)
			if(data[row][col]!='x')
				for(int dir=0; dir<4; ++dir){
					auto const result=compute({dir, row, col});
					/*
					std::cerr<<row<<' '<<col<<' '<<dir<<'-'
						<<result/numCol<<' '<<result%numCol<<'\n';
						*/
				}

	int const numPos=numRow*numCol;
	std::vector<int> distance_(numPos*numRobot*numRobot, INT_MAX);
	auto const distance=[&](int a, int b, int pos)->int&{
		assert(0<=a); assert(a<=b); assert(b<numRobot);
		assert((unsigned)pos<unsigned(numPos));
		return distance_[a+numRobot*(b+numRobot*pos)];
	};

	int result=INT_MAX;
	for(int a=numRobot; a--;){
		for(int b=a; b<numRobot; ++b){
			struct State{
				int pos, distance;
				bool operator<(State it) const{return distance>it.distance;}
			};
			std::priority_queue<State> queue;

			if(a==b){
				//for(int pos=0; pos<numPos; ++pos)
				for(int row=0; row<numRow; ++row)
					for(int col=0; col<numCol; ++col){
						assert(distance(a, a, Pos{row, col}.index())==INT_MAX);
						if(data[row][col]==char('1'+a)){
							auto const pos=Pos{row, col}.index();
							queue.push({pos, distance(a, a, pos)=0});
						}
					}
			}else{
				for(int pos=0; pos<numPos; ++pos){
					unsigned t=INT_MAX;
					for(int m=a; m<b; ++m)
						t=std::min(t, (unsigned)distance(a, m, pos)+
								distance(m+1, b, pos));
					assert(distance(a, b, pos)==INT_MAX);
					if(t<INT_MAX){
						if(b==numRobot-1 and a==0)
							result=std::min(result, (int)t);
						else
							queue.push({pos, distance(a, b, pos)=t});
					}
				}
			}

			while(not queue.empty()){
				auto [pos, curDistance]=queue.top(); queue.pop();
				if(curDistance!=distance(a, b, pos)) continue;
				for(int dir=0; dir<4; ++dir){
					auto const next=getMemory(pos, dir);
					if(next!=loop and distance(a, b, next)>curDistance+1){
						queue.push({next, distance(a, b, next)=curDistance+1});
					}
				}
			}
		}
	}
	std::cout<<(result==INT_MAX ? -1: result)<<'\n';
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:83:17: warning: unused variable 'result' [-Wunused-variable]
   83 |      auto const result=compute({dir, row, col});
      |                 ^~~~~~
robots.cpp: In member function 'std::pair<int, int> State::dirVector() const':
robots.cpp:29:2: warning: control reaches end of non-void function [-Wreturn-type]
   29 |  }
      |  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 1 ms 288 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 1 ms 288 KB Output is correct
11 Correct 252 ms 30348 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 54 ms 19320 KB Output is correct
14 Correct 656 ms 30788 KB Output is correct
15 Correct 160 ms 30156 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 1 ms 288 KB Output is correct
11 Correct 252 ms 30348 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 54 ms 19320 KB Output is correct
14 Correct 656 ms 30788 KB Output is correct
15 Correct 160 ms 30156 KB Output is correct
16 Correct 339 ms 84088 KB Output is correct
17 Execution timed out 1553 ms 85444 KB Time limit exceeded
18 Halted 0 ms 0 KB -