Submission #951556

#TimeUsernameProblemLanguageResultExecution timeMemory
951556GrindMachineNavigation 2 (JOI21_navigation2)C++17
75 / 100
600 ms2460 KiB
#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; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* refs: edi https://codeforces.com/blog/entry/88748?#comment-774016 (this thread) */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; #include "Anna.h" void Anna(int n, int k, std::vector<int> R, std::vector<int> C) { int a[n][n]; rep(i,n) rep(j,n) a[i][j] = 1; rep(i,n){ rep(j,n){ int ind = (i%3)*3+(j%3); if(!ind){ a[i][j] = 14; } else{ if(ind <= k){ int r = R[ind-1], c = C[ind-1]; int d = max(abs(i-r),abs(j-c)); if(d > 1){ // (i,j+1) if(j+2 <= c){ a[i][j] = 10; } // (i,j-1) else if(j-2 >= c){ a[i][j] = 11; } // (i+1,j) else if(i+2 <= r){ a[i][j] = 12; } // (i-1,j) else if(i-2 >= r){ a[i][j] = 13; } else{ assert(0); } } else{ int d1 = i-r+1, d2 = j-c+1; a[i][j] = (d1*3)+d2+1; } } } } } rep(i,n){ rep(j,n){ // cout << a[i][j] << " "; SetFlag(i,j,a[i][j]); } // cout << endl; } }
#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; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* refs: edi https://codeforces.com/blog/entry/88748?#comment-774016 (this thread) */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; #include "Bruno.h" std::vector<int> Bruno(int k, std::vector<int> values) { int a[3][3]; memset(a,0,sizeof a); rep(i,sz(values)){ a[i/3][i%3] = values[i]; } // rep(i,3){ // rep(j,3){ // cout << a[i][j] << " "; // } // cout << endl; // } // cout << endl; int zi = -1, zj = -1; rep(i,3){ rep(j,3){ if(a[i][j] == 14){ assert(zi == -1); zi = i, zj = j; } } } assert(zi != -1); int label[3][3]; label[zi][zj] = 0; rep1(iter,8){ if(iter%3 == 0){ zi = (zi+1)%3; } zj = (zj+1)%3; label[zi][zj] = iter; } vector<pii> cells = {{1,2},{1,0},{2,1},{0,1}}; vector<int> di = {0,0,1,-1,0}; vector<int> dj = {1,-1,0,0,0}; vector<int> ans(k); rep(i,3){ rep(j,3){ int ind = label[i][j]; if(!ind or ind > k) conts; ind--; pii cell = {-1,-1}; if(a[i][j] > 9){ int x = a[i][j]-10; ans[ind] = x; conts; } else{ int v = a[i][j]-1; cell = {i,j}; auto &[r,c] = cell; if(v == 0){ r++, c++; } if(v == 1){ r++; } if(v == 2){ r++, c--; } if(v == 3){ c++; } if(v == 4){ } if(v == 5){ c--; } if(v == 6){ r--, c++; } if(v == 7){ r--; } if(v == 8){ r--, c--; } } // cout << cell.ff << " " << cell.ss << endl; auto [r,c] = cell; int dir = 4; // cout << i << " " << j << endl; // cout << r << " " << c << endl; // (i,j+1) if(1 < c){ dir = 0; } // (i,j-1) else if(1 > c){ dir = 1; } // (i+1,j) else if(1 < r){ dir = 2; } else if(1 > r){ dir = 3; } ans[ind] = dir; } } // cout << endl; // rep(i,k){ // cout << ans[i] << " "; // } // cout << endl; return ans; // int b[3][3]; // vector<int> ans; // rep(x,k){ // rep(i,3){ // rep(j,3){ // int &mask = a[i][j]; // b[i][j] = mask%3; // mask /= 3; // } // } // int final_dir = 4; // rep(dir,4){ // auto [i,j] = cells[dir]; // if((b[i][j]+1)%3 == b[1][1]){ // final_dir = dir; // } // } // ans.pb(final_dir); // } // return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...