oj.uz

Submission #733568

# Submission time Handle Problem Language Result Execution time Memory
733568 2023-05-01T03:40:32 Z minhcool Mars (APIO22_mars) C++17
6 / 100
 21 ms 11596 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
 
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 = 0; i < (2 * n + 1); i++){
		for(int j = 0; j < (2 * n + 1); 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(0LL, min(k, (i - 1) / 2)), j - 2 * max(0LL, min(k, (j - 1) / 2))});
				bool ck = 1;
				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(cnt[id][lst.fi + temp1][lst.se + temp2][k] >= 100) continue;
						route[id][i][j].pb({lst.fi + temp1, lst.se + temp2});
						ck = 0;
						break;
					}
				}
			}
			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]++;
				itr++;
			}
		}	
	}
	for(int i = 0; i <= 2 * n; i++){
		for(int j = 0; j <= 2 * n; j++){
			for(int k = 0; k < n; k++){
				for(int kk = 0; kk < cnt[id][i][j][k]; kk++){
					//cout << i << " " << j << " " << k << " " << kk << " " << save[i][j][k][kk].fi << " " << save[i][j][k][kk].se << "\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){
	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';
		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;
      |                ~~~~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11324 KB Output is correct
2 Correct 14 ms 11284 KB Output is correct
3 Correct 14 ms 11060 KB Output is correct
4 Correct 15 ms 11596 KB Output is correct
5 Correct 16 ms 11340 KB Output is correct
6 Correct 16 ms 11096 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11324 KB Output is correct
2 Correct 14 ms 11284 KB Output is correct
3 Correct 14 ms 11060 KB Output is correct
4 Correct 15 ms 11596 KB Output is correct
5 Correct 16 ms 11340 KB Output is correct
6 Correct 16 ms 11096 KB Output is correct
7 Runtime error 21 ms 2912 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11324 KB Output is correct
2 Correct 14 ms 11284 KB Output is correct
3 Correct 14 ms 11060 KB Output is correct
4 Correct 15 ms 11596 KB Output is correct
5 Correct 16 ms 11340 KB Output is correct
6 Correct 16 ms 11096 KB Output is correct
7 Runtime error 21 ms 2912 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11324 KB Output is correct
2 Correct 14 ms 11284 KB Output is correct
3 Correct 14 ms 11060 KB Output is correct
4 Correct 15 ms 11596 KB Output is correct
5 Correct 16 ms 11340 KB Output is correct
6 Correct 16 ms 11096 KB Output is correct
7 Runtime error 21 ms 2912 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11324 KB Output is correct
2 Correct 14 ms 11284 KB Output is correct
3 Correct 14 ms 11060 KB Output is correct
4 Correct 15 ms 11596 KB Output is correct
5 Correct 16 ms 11340 KB Output is correct
6 Correct 16 ms 11096 KB Output is correct
7 Runtime error 21 ms 2912 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11324 KB Output is correct
2 Correct 14 ms 11284 KB Output is correct
3 Correct 14 ms 11060 KB Output is correct
4 Correct 15 ms 11596 KB Output is correct
5 Correct 16 ms 11340 KB Output is correct
6 Correct 16 ms 11096 KB Output is correct
7 Runtime error 21 ms 2912 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11324 KB Output is correct
2 Correct 14 ms 11284 KB Output is correct
3 Correct 14 ms 11060 KB Output is correct
4 Correct 15 ms 11596 KB Output is correct
5 Correct 16 ms 11340 KB Output is correct
6 Correct 16 ms 11096 KB Output is correct
7 Runtime error 21 ms 2912 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11324 KB Output is correct
2 Correct 14 ms 11284 KB Output is correct
3 Correct 14 ms 11060 KB Output is correct
4 Correct 15 ms 11596 KB Output is correct
5 Correct 16 ms 11340 KB Output is correct
6 Correct 16 ms 11096 KB Output is correct
7 Runtime error 21 ms 2912 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11324 KB Output is correct
2 Correct 14 ms 11284 KB Output is correct
3 Correct 14 ms 11060 KB Output is correct
4 Correct 15 ms 11596 KB Output is correct
5 Correct 16 ms 11340 KB Output is correct
6 Correct 16 ms 11096 KB Output is correct
7 Runtime error 21 ms 2912 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11324 KB Output is correct
2 Correct 14 ms 11284 KB Output is correct
3 Correct 14 ms 11060 KB Output is correct
4 Correct 15 ms 11596 KB Output is correct
5 Correct 16 ms 11340 KB Output is correct
6 Correct 16 ms 11096 KB Output is correct
7 Runtime error 21 ms 2912 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -