| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 733715 |
2023-05-01T08:25:07 Z |
minhcool |
Mars (APIO22_mars) |
C++17 |
|
1 ms |
1352 KB |
#include "mars.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 35;
const int oo = 1e18 + 7, mod = 1e9 + 7;
vector<ii> route[N][N][N];
int cnt[N][N][N][N];
ii save[N][N][N][N][105];// cell (i, j) at phase k, the h-th bit will save the value of what node
int mx = -1;
bool cmp(pair<int, ii> a, pair<int, ii> b){
if(a.fi != b.fi) return a.fi < b.fi;
else return a.se > b.se;
}
void prep(int id){// preparing the route for (i, j)
// in order to get 36, we don't need the SA the path
int n = id;
for(int i = 0; i < (2 * n + 1); i++){
for(int j = 0; j < (2 * n + 1); j++){
route[id][i][j].clear();
for(int k = 0; k < (2 * n + 1); k++) cnt[id][i][j][k] = 0;
}
}
for(int i = 2 * n; i >= 0; i--){
for(int j = 2 * n; j >= 0; j--){
ii lst = {i, j};
route[id][i][j].pb({i, j});
for(int k = 1; k < n; k++){
route[id][i][j].pb({i - 2 * max(0, min(k, (i - 1) / 2)), j - 2 * max(0, min(k, (j - 1) / 2))});
/*
bool ck = 1;
vector<pair<int, ii>> cans;
for(int temp1 = -2; temp1 <= 0; temp1++){
if(!ck) break;
for(int temp2 = -2; temp2 <= 0; temp2++){
if((lst.fi + temp1) < 0 || (lst.se + temp2) < 0) continue;
if((lst.fi + temp1) > (2 * n - 2 * k) || (lst.se + temp2) > (2 * n - 2 * k)) continue;
if(cnt[id][lst.fi + temp1][lst.se + temp2][k] >= 100) continue;
cans.pb({cnt[id][lst.fi + temp1][lst.se + temp2][k] - 10 * (temp1 + temp2), {lst.fi + temp1, lst.se + temp2}});
//ck = 0;
//break;
}
}
sort(cans.begin(), cans.end(), cmp);
route[id][i][j].pb({cans[0].se.fi, cans[0].se.se});
lst = {cans[0].se.fi, cans[0].se.se};
*/
//assert(!ck);
}
int itr = 0;
for(auto it : route[id][i][j]){
//cout << i << " " << j << " " << it.fi << " " << it.se << " " << itr << "\n";
save[id][it.fi][it.se][itr][cnt[id][it.fi][it.se][itr]] = {i, j};
cnt[id][it.fi][it.se][itr]++;
mx = max(mx, cnt[id][it.fi][it.se][itr]);
//if(mx > 100) cout << mx << "\n";
itr++;
}
}
}
for(int i = 0; i <= 2 * n; i++){
for(int j = 0; j <= 2 * n; j++){
// cout << i << " " << j << " " << cnt[id][i][j][9] << " " << cnt[id][i][j][10] << "\n";
/*
for(int k = 0; k < n; k++){
cout << id << " " << i << " " << j << " " << k << " " << cnt[id][i][j][k] << "\n";
}*/
}
}
}
bool vis[N][N];
int val[N][N];
void ff(int i, int j, int n){
//cout << i << " " << j << "\n";
if(i < 0 || j < 0 || i >= (2 * n + 1) || j >= (2 * n + 1) || !val[i][j]) return;
val[i][j] = 0;
ff(i + 1, j, n);
ff(i - 1, j, n);
ff(i, j - 1, n);
ff(i, j + 1, n);
}
string process(vector<vector<string>> a, int i, int j, int k, int n){
if(!(i + j + k)) prep(n);
//cout << "OK\n";
for(int ii = 0; ii <= 2 * n; ii++){
for(int jj = 0; jj <= 2 * n; jj++) vis[ii][jj] = 0;
}
for(int ii = 0; ii <= 2; ii++){
for(int jj = 0; jj <= 2; jj++){
for(int kk = 0; kk < cnt[n][i + ii][j + jj][k]; kk++){
int x = save[n][i + ii][j + jj][k][kk].fi, y = save[n][i + ii][j + jj][k][kk].se;
val[x][y] = a[ii][jj][kk] - '0';
vis[x][y] = 1;
//cout << i << " " << j << " " << k << " " << x << " " << y << " " << val[x][y] << "\n";
}
}
}
if(k == n - 1){
//exit(0);
int ans = 0;
/*
for(int i = 0; i < (2 * n) + 1; i++){
for(int j = 0; j < (2 * n) + 1; j++) cout << val[i][j] << " ";
cout << "\n";
}*/
for(int i = 0; i < (2 * n + 1); i++){
for(int j = 0; j < (2 * n + 1); j++){
assert(vis[i][j]);
// cout << "OK " << i << " " << j << " " << val[i][j] << "\n";
if(!val[i][j]) continue;
ans++;
ff(i, j, n);
}
}
//cout << ans << "\n";
string temp;
for(int kk = 0; kk < 100; kk++) temp += '0';
for(int kk = 0; kk < 20; kk++) if(ans & (1LL << kk)) temp[kk] = '1';
//cout << mx << "\n";
return temp;
}
else{
string temp;
for(int kk = 0; kk < 100; kk++) temp += '0';
for(int kk = 0; kk < cnt[n][i][j][k + 1]; kk++){
int x = save[n][i][j][k + 1][kk].fi, y = save[n][i][j][k + 1][kk].se;
assert(vis[x][y]);
temp[kk] = char(48 + val[x][y]);
}
return temp;
}
}
Compilation message
mars.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
mars.cpp: In function 'void prep(int)':
mars.cpp:40:7: warning: variable 'lst' set but not used [-Wunused-but-set-variable]
40 | ii lst = {i, j};
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1352 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1352 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1352 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1352 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1352 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1352 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1352 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1352 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1352 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1352 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
