# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
951571 | GrindMachine | Navigation 2 (JOI21_navigation2) | C++17 | 563 ms | 2400 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
vector<bool> used(10);
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;
used[a[i][j]] = 1;
}
}
}
}
}
int unused = -1;
rep1(i,9){
if(!used[i]){
unused = i;
break;
}
}
assert(unused != -1);
assert(unused <= 8);
rep(i,n){
rep(j,n){
int ind = (i%3)*3+(j%3);
if(ind == 8){
a[i][j] = unused;
}
else{
if(a[i][j] > unused){
a[i][j]--;
}
}
}
}
rep(i,n){
rep(j,n){
SetFlag(i,j,a[i][j]);
}
}
}
#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];
}
int zi = -1, zj = -1;
rep(i,3){
rep(j,3){
if(a[i][j] == 13){
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;
}
int unused = a[zi][zj];
rep(i,3){
rep(j,3){
if(a[i][j] >= unused){
a[i][j]++;
}
}
}
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--;
}
}
auto [r,c] = cell;
int dir = 4;
// (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;
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |