Submission #320487

#TimeUsernameProblemLanguageResultExecution timeMemory
320487monus1042Board (CEOI13_board)C++17
20 / 100
7 ms3564 KiB
// NK #include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; typedef pair<int,int> ii; typedef long long ll; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<ll> vll; #define pb push_back #define eb emplace_back #define pob pop_back #define psf push_front #define pof pop_front #define mkp make_pair #define mkt make_tuple #define all(x) x.begin(), x.end() #define Bolivia_is_nice ios::sync_with_stdio(false), cin.tie(nullptr) //typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ord_set; const int MAXS = 4100 * 3; vi g[MAXS]; bool vis[MAXS]; int findlocation(string a, int A){ for (int i=0; i<a.size(); i++){ if (a[i] == '1'){ A = A*2; } if (a[i] == '2'){ A = A*2+1; } if (a[i] == 'L'){ A = A-1; } if (a[i] == 'R'){ A = A+1; } if (a[i] == 'U'){ A = A/2; } } return A; } void solve(){ string a,b; cin>>a>>b; for (int i=1; i<MAXS-5; i++){ int l = i*2, r = i*2+1; if (l < MAXS) g[i].pb(l), g[l].pb(i); if (r < MAXS) g[i].pb(r), g[r].pb(i); if (i > 1){ int cnt = 0; for (int j=0; j<=10; j++){ if (i&(1<<j)) ++cnt; } if (cnt == 1){ g[i].pb(i+1); g[i+1].pb(i); }else{ bool sw = 0, ok = 1; for (int j=10; j>=0; j--){ if (i&(1<<j) && sw == 0){ sw = 1; } else if (!(i&(1<<j)) && sw){ ok = 0; } } if (ok){ g[i].pb(i-1); g[i-1].pb(i); }else{ g[i].pb(i-1); g[i-1].pb(i); g[i].pb(i+1); g[i+1].pb(i); } } } } int A=findlocation(a, 1), B=findlocation(b, 1); queue<ii> bfs; // node, distance bfs.push(ii(A, 0)); vis[A] = 1; while(!bfs.empty()){ int u = bfs.front().first; int d = bfs.front().second; bfs.pop(); if (u == B){ cout<<d<<'\n'; return; } for (int i=0; i<g[u].size(); i++){ int v = g[u][i]; if (!vis[v]){ vis[v] = 1; bfs.push(ii(v, d+1)); } } } } int main(){ Bolivia_is_nice; int t = 1; //cin>>t; while(t--) solve(); return 0; } /* ~/.emacs */

Compilation message (stderr)

board.cpp: In function 'int findlocation(std::string, int)':
board.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i=0; i<a.size(); i++){
      |                ~^~~~~~~~~
board.cpp: In function 'void solve()':
board.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for (int i=0; i<g[u].size(); i++){
      |                 ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...