| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 805546 |
2023-08-03T17:44:41 Z |
Antekb |
Wombats (IOI13_wombats) |
C++17 |
|
0 ms |
0 KB |
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int RMAX=5000, CMAX=200, BLOMAX=130;
int H[RMAX][CMAX], V[RMAX][CMAX], R, C, K=43, blo;
int dist[2*BLOMAX][CMAX][CMAX], pocz[BLOMAX], kon[BLOMAX], czy[BLOMAX*2];
int escape(int V1, int V2) {
int ans=dist[1][V1][V2];
int sum=0;
for(int i=V2+1; i<C; i++){
sum+=H[R-1][i-1];
ans=min(ans, dist[1][V1][i]+sum);
}
sum=0;
for(int i=V2-1; i>=0; i--){
sum+=H[R-1][i];
ans=min(ans, dist[1][V1][i]+sum);
}#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int RMAX=5000, CMAX=200, BLOMAX=130;
int H[RMAX][CMAX], V[RMAX][CMAX], R, C, K=43, blo;
int dist[2*BLOMAX][CMAX][CMAX], pocz[BLOMAX], kon[BLOMAX], czy[BLOMAX*2];
int res[CMAX][CMAX];
void get_res(){
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
res[i][j]=dist[1][i][j];
}
for(int j=1; j<C; j++){
res[i][j]=min(res[i][j], res[i][j-1]+H[R-1][j-1]);
}
for(int j=C-2; j>=0; j--){
res[i][j]=min(res[i][j+1]+H[R-1][j], res[i][j]);
}
}
}
int escape(int V1, int V2) {
/*int ans=dist[1][V1][V2];
int sum=0;
for(int i=V2+1; i<C; i++){
sum+=H[R-1][i-1];
ans=min(ans, dist[1][V1][i]+sum);
}
sum=0;
for(int i=V2-1; i>=0; i--){
sum+=H[R-1][i];
ans=min(ans, dist[1][V1][i]+sum);
}*/
//cerr<<ans<<"\n";
return res[V1][V2];
}
void update(int num){
int tab[C][C];
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
tab[i][j]=(1e9)*(i!=j);
}
}
for(int r=pocz[num]; r<=kon[num]; r++){
for(int i=0; i<C; i++){
for(int j=1; j<C; j++){
tab[i][j]=min(tab[i][j], tab[i][j-1]+H[r][j-1]);
}
for(int j=C-2; j>=0; j--){
tab[i][j]=min(tab[i][j+1]+H[r][j], tab[i][j]);
}
for(int j=0; j<C; j++){
tab[i][j]+=V[r][j];
}
}
}
//cerr<<"\n";
//cerr<<num<<"\n";
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
//cerr<<tab[i][j]<<" \n"[j==C-1];
dist[blo+num][i][j]=tab[i][j];
}
}
//cerr<<"\n";
}
void lacz(int v){
if(!czy[v])return;
int l=v+v, r=v+v+1;
if(!czy[r]){
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
dist[v][i][j]=dist[l][i][j];
}
}
}
else{
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
dist[v][i][j]=1e9;
for(int k=0; k<C; k++){
dist[v][i][j]=min(dist[v][i][j], dist[l][i][k]+dist[r][k][j]);
}
}
}
}
/*cerr<<"\n";
cerr<<v<<"a\n";
cerr<<l<<" "<<r<<"\n";
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<dist[v][i][j]<<" \n"[j==C-1];
}
}
cerr<<"\n";*/
}
void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
R=_R;
C=_C;
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
H[i][j]=_H[i][j];
V[i][j]=_V[i][j];
}
}
for(int i=0; i*K<R-1; i++){
blo++;
}
while(__builtin_popcount(blo)>1)blo++;
for(int i=0; i*K<R-1; i++){
pocz[i]=i*K;
kon[i]=min((i+1)*K-1, R-2);
update(i);
czy[i+blo]=1;
}
for(int i=blo-1; i>0; i--){
czy[i]=(czy[i+i]|czy[i+i+1]);
lacz(i);
}
get_res();
/*for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
}
}*/
}
void changeH(int P, int Q, int W) {
H[P][Q]=W;
if(P!=R-1){
update(P/K);
int v=P/K+blo;
v/=2;
while(v){
lacz(v);
v/=2;
}
}
get_res();
/*for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
}
}*/
}
void changeV(int P, int Q, int W) {
V[P][Q]=W;
update(P/K);
int v=P/K+blo;
v/=2;
while(v){
lacz(v);
v/=2;
}
get_res();
/*for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
}
}*/
}
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
tab[i][j]=(1e9)*(i!=j);
}
}
for(int r=pocz[num]; r<=kon[num]; r++){
for(int i=0; i<C; i++){
for(int j=1; j<C; j++){
tab[i][j]=min(tab[i][j], tab[i][j-1]+H[r][j-1]);
}
for(int j=C-2; j>=0; j--){
tab[i][j]=min(tab[i][j+1]+H[r][j], tab[i][j]);
}
for(int j=0; j<C; j++){
tab[i][j]+=V[r][j];
}
}
}
//cerr<<"\n";
//cerr<<num<<"\n";
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
//cerr<<tab[i][j]<<" \n"[j==C-1];
dist[blo+num][i][j]=tab[i][j];
}
}
//cerr<<"\n";
}
void lacz(int v){
if(!czy[v])return;
int l=v+v, r=v+v+1;
if(!czy[r]){
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
dist[v][i][j]=dist[l][i][j];
}
}
}
else{
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
dist[v][i][j]=1e9;
for(int k=0; k<C; k++){
dist[v][i][j]=min(dist[v][i][j], dist[l][i][k]+dist[r][k][j]);
}
}
}
}
/*cerr<<"\n";
cerr<<v<<"a\n";
cerr<<l<<" "<<r<<"\n";
for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<dist[v][i][j]<<" \n"[j==C-1];
}
}
cerr<<"\n";*/
}
void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
R=_R;
C=_C;
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
H[i][j]=_H[i][j];
V[i][j]=_V[i][j];
}
}
for(int i=0; i*K<R-1; i++){
blo++;
}
while(__builtin_popcount(blo)>1)blo++;
for(int i=0; i*K<R-1; i++){
pocz[i]=i*K;
kon[i]=min((i+1)*K-1, R-2);
update(i);
czy[i+blo]=1;
}
for(int i=blo-1; i>0; i--){
czy[i]=(czy[i+i]|czy[i+i+1]);
lacz(i);
}
/*for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
}
}*/
}
void changeH(int P, int Q, int W) {
H[P][Q]=W;
if(P!=R-1){
update(P/K);
int v=P/K+blo;
v/=2;
while(v){
lacz(v);
v/=2;
}
}
/*for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
}
}*/
}
void changeV(int P, int Q, int W) {
V[P][Q]=W;
update(P/K);
int v=P/K+blo;
v/=2;
while(v){
lacz(v);
v/=2;
}
/*for(int i=0; i<C; i++){
for(int j=0; j<C; j++){
cerr<<i<<" "<<j<<" "<<escape(i, j)<<"\n";
}
}*/
}
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
15 | int res;
| ^~~
wombats.cpp:18:3: error: stray '#' in program
18 | }#include "wombats.h"
| ^
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:18:4: error: 'include' was not declared in this scope
18 | }#include "wombats.h"
| ^~~~~~~
wombats.cpp:25:15: error: a function-definition is not allowed here before '{' token
25 | void get_res(){
| ^
wombats.cpp:38:28: error: a function-definition is not allowed here before '{' token
38 | int escape(int V1, int V2) {
| ^
wombats.cpp:53:21: error: a function-definition is not allowed here before '{' token
53 | void update(int num){
| ^
wombats.cpp:83:17: error: a function-definition is not allowed here before '{' token
83 | void lacz(int v){
| ^
wombats.cpp:114:65: error: a function-definition is not allowed here before '{' token
114 | void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
| ^
wombats.cpp:144:35: error: a function-definition is not allowed here before '{' token
144 | void changeH(int P, int Q, int W) {
| ^
wombats.cpp:163:35: error: a function-definition is not allowed here before '{' token
163 | void changeV(int P, int Q, int W) {
| ^
wombats.cpp:184:4: error: 'tab' was not declared in this scope; did you mean 'tan'?
184 | tab[i][j]=(1e9)*(i!=j);
| ^~~
| tan
wombats.cpp:187:17: error: 'num' was not declared in this scope; did you mean 'sum'?
187 | for(int r=pocz[num]; r<=kon[num]; r++){
| ^~~
| sum
wombats.cpp:190:5: error: 'tab' was not declared in this scope; did you mean 'tan'?
190 | tab[i][j]=min(tab[i][j], tab[i][j-1]+H[r][j-1]);
| ^~~
| tan
wombats.cpp:193:5: error: 'tab' was not declared in this scope; did you mean 'tan'?
193 | tab[i][j]=min(tab[i][j+1]+H[r][j], tab[i][j]);
| ^~~
| tan
wombats.cpp:196:5: error: 'tab' was not declared in this scope; did you mean 'tan'?
196 | tab[i][j]+=V[r][j];
| ^~~
| tan
wombats.cpp:205:13: error: 'num' was not declared in this scope; did you mean 'sum'?
205 | dist[blo+num][i][j]=tab[i][j];
| ^~~
| sum
wombats.cpp:205:24: error: 'tab' was not declared in this scope; did you mean 'tan'?
205 | dist[blo+num][i][j]=tab[i][j];
| ^~~
| tan
wombats.cpp:22:35: warning: unused variable 'R' [-Wunused-variable]
22 | int H[RMAX][CMAX], V[RMAX][CMAX], R, C, K=43, blo;
| ^
wombats.cpp:22:41: warning: unused variable 'K' [-Wunused-variable]
22 | int H[RMAX][CMAX], V[RMAX][CMAX], R, C, K=43, blo;
| ^
wombats.cpp:23:60: warning: unused variable 'czy' [-Wunused-variable]
23 | int dist[2*BLOMAX][CMAX][CMAX], pocz[BLOMAX], kon[BLOMAX], czy[BLOMAX*2];
| ^~~
wombats.cpp:24:5: warning: unused variable 'res' [-Wunused-variable]
24 | int res[CMAX][CMAX];
| ^~~
wombats.cpp:209:1: warning: no return statement in function returning non-void [-Wreturn-type]
209 | }
| ^
wombats.cpp: In function 'void init(int, int, int (*)[200], int (*)[200])':
wombats.cpp:257:3: error: 'update' was not declared in this scope
257 | update(i);
| ^~~~~~
wombats.cpp: In function 'void changeH(int, int, int)':
wombats.cpp:273:3: error: 'update' was not declared in this scope
273 | update(P/K);
| ^~~~~~
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:290:2: error: 'update' was not declared in this scope
290 | update(P/K);
| ^~~~~~
