oj.uz

Submission #60234

# Submission time Handle Problem Language Result Execution time Memory
60234 2018-07-23T22:17:00 Z spencercompton Wombats (IOI13_wombats) C++17
37 / 100
 20000 ms 18456 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];
pair<int, int> pre[200][200];
int upd = 0;
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] = make_pair(-1,-1);
		}
	}
}
 
void changeH(int P, int Q, int W) {
	rig[P][Q] = W;
	upd++;
}
 
void changeV(int P, int Q, int W) {
	sum += (W-bel[P][Q]);
	bel[P][Q] = W;
	upd++;
}
 
int escape(int V1, int V2) {
	if(c==1){
		return sum;
	}
	if(pre[V1][V2].second==upd){
		return pre[V1][V2].first;
	}
	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] = make_pair(zz,upd);
				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 10 ms 8184 KB Output is correct
2 Correct 11 ms 8292 KB Output is correct
3 Correct 124 ms 10008 KB Output is correct
4 Correct 14 ms 10008 KB Output is correct
5 Correct 12 ms 10008 KB Output is correct
6 Correct 2 ms 10008 KB Output is correct
7 Correct 2 ms 10008 KB Output is correct
8 Correct 3 ms 10008 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10008 KB Output is correct
2 Correct 2 ms 10008 KB Output is correct
3 Correct 2 ms 10008 KB Output is correct
4 Correct 14 ms 10008 KB Output is correct
5 Correct 12 ms 10008 KB Output is correct
6 Correct 53 ms 10008 KB Output is correct
7 Correct 30 ms 10008 KB Output is correct
8 Correct 35 ms 10008 KB Output is correct
9 Correct 44 ms 10008 KB Output is correct
10 Correct 35 ms 10008 KB Output is correct
11 Correct 136 ms 10008 KB Output is correct
12 Correct 36 ms 10008 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 10008 KB Output is correct
2 Correct 68 ms 10008 KB Output is correct
3 Correct 131 ms 10008 KB Output is correct
4 Correct 129 ms 10008 KB Output is correct
5 Correct 130 ms 10008 KB Output is correct
6 Correct 3 ms 10008 KB Output is correct
7 Correct 2 ms 10008 KB Output is correct
8 Correct 3 ms 10008 KB Output is correct
9 Correct 86 ms 10008 KB Output is correct
10 Correct 2 ms 10008 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10935 ms 17424 KB Output is correct
2 Correct 1020 ms 17436 KB Output is correct
3 Correct 10296 ms 17568 KB Output is correct
4 Execution timed out 20011 ms 18408 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 18408 KB Output is correct
2 Correct 75 ms 18408 KB Output is correct
3 Correct 129 ms 18408 KB Output is correct
4 Correct 125 ms 18408 KB Output is correct
5 Correct 121 ms 18408 KB Output is correct
6 Correct 11199 ms 18408 KB Output is correct
7 Correct 1204 ms 18408 KB Output is correct
8 Correct 11323 ms 18408 KB Output is correct
9 Execution timed out 20096 ms 18456 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 18456 KB Output is correct
2 Correct 61 ms 18456 KB Output is correct
3 Correct 123 ms 18456 KB Output is correct
4 Correct 174 ms 18456 KB Output is correct
5 Correct 170 ms 18456 KB Output is correct
6 Correct 10536 ms 18456 KB Output is correct
7 Correct 1188 ms 18456 KB Output is correct
8 Correct 11048 ms 18456 KB Output is correct
9 Execution timed out 20047 ms 18456 KB Time limit exceeded
10 Halted 0 ms 0 KB -