oj.uz

Submission #60238

# Submission time Handle Problem Language Result Execution time Memory
60238 2018-07-23T22:22:25 Z spencercompton Wombats (IOI13_wombats) C++17
37 / 100
 20000 ms 17340 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;
int vals[2][2];
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(c<=2 && y==r-1){
				pre[V1][x] = make_pair(zz,upd);
			}
			else 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:66: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 8 ms 8196 KB Output is correct
2 Correct 13 ms 8196 KB Output is correct
3 Correct 109 ms 9956 KB Output is correct
4 Correct 10 ms 9956 KB Output is correct
5 Correct 9 ms 9956 KB Output is correct
6 Correct 3 ms 9956 KB Output is correct
7 Correct 2 ms 9956 KB Output is correct
8 Correct 3 ms 9956 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9956 KB Output is correct
2 Correct 4 ms 9956 KB Output is correct
3 Correct 2 ms 9956 KB Output is correct
4 Correct 14 ms 9956 KB Output is correct
5 Correct 12 ms 9956 KB Output is correct
6 Correct 60 ms 9956 KB Output is correct
7 Correct 27 ms 9956 KB Output is correct
8 Correct 36 ms 9956 KB Output is correct
9 Correct 42 ms 9956 KB Output is correct
10 Correct 43 ms 9956 KB Output is correct
11 Correct 175 ms 9956 KB Output is correct
12 Correct 45 ms 9956 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 9956 KB Output is correct
2 Correct 89 ms 9956 KB Output is correct
3 Correct 143 ms 9956 KB Output is correct
4 Correct 148 ms 9956 KB Output is correct
5 Correct 136 ms 9956 KB Output is correct
6 Correct 2 ms 9956 KB Output is correct
7 Correct 3 ms 9956 KB Output is correct
8 Correct 2 ms 9956 KB Output is correct
9 Correct 93 ms 9956 KB Output is correct
10 Correct 3 ms 9956 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20004 ms 17320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 17320 KB Output is correct
2 Correct 74 ms 17320 KB Output is correct
3 Correct 141 ms 17320 KB Output is correct
4 Correct 171 ms 17320 KB Output is correct
5 Correct 130 ms 17320 KB Output is correct
6 Execution timed out 20025 ms 17320 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 17320 KB Output is correct
2 Correct 76 ms 17320 KB Output is correct
3 Correct 130 ms 17320 KB Output is correct
4 Correct 127 ms 17320 KB Output is correct
5 Correct 152 ms 17320 KB Output is correct
6 Execution timed out 20076 ms 17340 KB Time limit exceeded
7 Halted 0 ms 0 KB -