oj.uz

Submission #59672

# Submission time Handle Problem Language Result Execution time Memory
59672 2018-07-22T21:43:06 Z spencercompton Wombats (IOI13_wombats) C++17
37 / 100
 20000 ms 18760 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
int bel[5000][200];
int rig[5000][200];
int r, c;
bool v[5000][200];
int pre[5000][200];
bool upd = false;;
int sum = 0;
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++){
			if(i+1<r){
				bel[i][j] = V[i][j];
				sum += V[i][j];
			}
			if(j+1<c){
				rig[i][j] = H[i][j];
			}
		}
	}
	for(int i = 0; i<c; i++){
		for(int j = 0; j<c; j++){
			pre[i][j] = -1;
		}
	}
}
 
void changeH(int P, int Q, int W) {
	rig[P][Q] = W;
	upd = true;
}
 
void changeV(int P, int Q, int W) {
	sum += (W-bel[P][Q]);
	bel[P][Q] = W;
	upd = true;
}
 
int escape(int V1, int V2) {
	if(c==1){
		return sum;
	}
	if(!upd && c<=20 && pre[V1][V2]!=-1){
		return pre[V1][V2];
	}
	int maxans = r + c;
	maxans *= 1000;
	vector<pair<int, int> > li[2000];
	li[0].push_back(make_pair(0,V1));
	for(int i = 0; i<r; i++){
		for(int j = 0; j<c; j++){
			v[i][j] = false;
		}
	}
	int mo[4000];
	for(int i = 0; i<4000; i++){
		mo[i] = i%2000;
	}
	for(int zz = 0;; zz++){
		int z = zz%2000;
		for(int i =0; i<li[z].size(); i++){
			int y = li[z][i].first;
			int x = li[z][i].second;
			if(y==r-1 && x==V2){
				pre[V1][V2] = zz;
				return zz;
			}
			if(v[y][x]){
				continue;
			}
			v[y][x] = true;
			int ny, nx;
			if(x>0){
				 ny = y;
				 nx = x-1; 
				if(!v[ny][nx]){
					li[mo[z+rig[ny][nx]]].push_back(make_pair(ny,nx));
				}
			}
			if(x<c-1){
				 ny = y;
				 nx = x+1;
				if(!v[ny][nx]){
					li[mo[z+rig[y][x]]].push_back(make_pair(ny,nx));
				}
			}
			if(y<r-1){
				 ny = y+1;
				 nx = x;
				if(!v[ny][nx]){
					li[mo[z+bel[y][x]]].push_back(make_pair(ny,nx));
				}
			}
		}
		li[z].clear();
	}
    return -1;
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i =0; i<li[z].size(); i++){
                 ~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 10 ms 8292 KB Output is correct
3 Correct 124 ms 10888 KB Output is correct
4 Correct 11 ms 10888 KB Output is correct
5 Correct 11 ms 10888 KB Output is correct
6 Correct 3 ms 10888 KB Output is correct
7 Correct 3 ms 10888 KB Output is correct
8 Correct 3 ms 10888 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10888 KB Output is correct
2 Correct 2 ms 10888 KB Output is correct
3 Correct 3 ms 10888 KB Output is correct
4 Correct 14 ms 10888 KB Output is correct
5 Correct 13 ms 10888 KB Output is correct
6 Correct 69 ms 10888 KB Output is correct
7 Correct 40 ms 10888 KB Output is correct
8 Correct 43 ms 10888 KB Output is correct
9 Correct 50 ms 10888 KB Output is correct
10 Correct 39 ms 10888 KB Output is correct
11 Correct 134 ms 10888 KB Output is correct
12 Correct 39 ms 10888 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 10888 KB Output is correct
2 Correct 66 ms 10888 KB Output is correct
3 Correct 138 ms 10888 KB Output is correct
4 Correct 168 ms 10888 KB Output is correct
5 Correct 121 ms 10888 KB Output is correct
6 Correct 3 ms 10888 KB Output is correct
7 Correct 2 ms 10888 KB Output is correct
8 Correct 3 ms 10888 KB Output is correct
9 Correct 102 ms 10888 KB Output is correct
10 Correct 3 ms 10888 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10749 ms 18740 KB Output is correct
2 Correct 904 ms 18740 KB Output is correct
3 Correct 10962 ms 18740 KB Output is correct
4 Execution timed out 20025 ms 18756 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 18756 KB Output is correct
2 Correct 70 ms 18756 KB Output is correct
3 Correct 146 ms 18756 KB Output is correct
4 Correct 136 ms 18756 KB Output is correct
5 Correct 157 ms 18756 KB Output is correct
6 Correct 10733 ms 18756 KB Output is correct
7 Correct 1255 ms 18756 KB Output is correct
8 Correct 10860 ms 18756 KB Output is correct
9 Execution timed out 20014 ms 18756 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 18756 KB Output is correct
2 Correct 72 ms 18756 KB Output is correct
3 Correct 121 ms 18756 KB Output is correct
4 Correct 120 ms 18756 KB Output is correct
5 Correct 119 ms 18756 KB Output is correct
6 Correct 11029 ms 18756 KB Output is correct
7 Correct 832 ms 18760 KB Output is correct
8 Correct 10942 ms 18760 KB Output is correct
9 Execution timed out 20031 ms 18760 KB Time limit exceeded
10 Halted 0 ms 0 KB -