Submission #263170

#TimeUsernameProblemLanguageResultExecution timeMemory
263170user202729Robots (APIO13_robots)C++17
100 / 100
1483 ms159556 KiB
// 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 (stderr)

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 |  }
      |  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...