oj.uz

Submission #263170

# Submission time Handle Problem Language Result Execution time Memory
263170 2020-08-13T13:48:50 Z user202729 Robots (APIO13_robots) C++17
100 / 100
 1483 ms 159556 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});
					(void) result;
					/*
					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)];
	};

	struct State{
		unsigned a: 4;
		unsigned b: 4;
		int pos: 32-8;
	};
	std::vector<std::vector<State>> queue(numPos);
	auto const update=[&](int curDistance, int a, int b, int pos){
		if(curDistance<distance(a, b, pos)){
			while(curDistance>=(int)queue.size()) queue.resize(queue.size()*2);
			queue[distance(a, b, pos)=curDistance].push_back({(char) a, (char) b, pos});
		}
	};

	int result=INT_MAX;
	for(int a=numRobot; a--;){
		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();
					update(0, a, a, pos);
				}
			}
	}

	for(int curDistance=0; curDistance<(int)queue.size(); ++curDistance){
		for(int index=0; index<(int)queue[curDistance].size(); ++index){
			auto [a, b, pos]=queue[curDistance][index];
			if(curDistance!=distance(a, b, pos)) continue;

			if(a==0 and b==numRobot-1){
				result=std::min(result, curDistance);
				continue;
			}

			for(int c=b+1; c<numRobot;++c){
				if(auto const d1=distance(b+1, c, pos); d1<=curDistance)
					update(curDistance+d1, a, c, pos);
			}
			for(int c=a; c--;){
				if(auto const d1=distance(c, a-1, pos); d1<=curDistance)
					update(curDistance+d1, c, b, pos);
			}

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

Compilation message

robots.cpp: In lambda function:
robots.cpp:108:54: warning: narrowing conversion of '(char)a' from 'char' to 'unsigned int' [-Wnarrowing]
  108 |    queue[distance(a, b, pos)=curDistance].push_back({(char) a, (char) b, pos});
      |                                                      ^~~~~~~~
robots.cpp:108:64: warning: narrowing conversion of '(char)b' from 'char' to 'unsigned int' [-Wnarrowing]
  108 |    queue[distance(a, b, pos)=curDistance].push_back({(char) a, (char) b, pos});
      |                                                                ^~~~~~~~
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 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 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 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 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 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 171 ms 37780 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 20 ms 21248 KB Output is correct
14 Correct 404 ms 54264 KB Output is correct
15 Correct 76 ms 34040 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 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 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 171 ms 37780 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 20 ms 21248 KB Output is correct
14 Correct 404 ms 54264 KB Output is correct
15 Correct 76 ms 34040 KB Output is correct
16 Correct 94 ms 89720 KB Output is correct
17 Correct 1483 ms 159556 KB Output is correct
18 Correct 237 ms 95220 KB Output is correct
19 Correct 79 ms 90104 KB Output is correct
20 Correct 986 ms 124396 KB Output is correct