oj.uz

Submission #410102

# Submission time Handle Problem Language Result Execution time Memory
410102 2021-05-22T02:37:02 Z rqi Wombats (IOI13_wombats) C++14
100 / 100
 6334 ms 192468 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long double db;
 
#define mp make_pair
#define f first
#define s second
#define pb push_back
 
#define sz(x) (int)(x).size()
 
const int MOD = 1e9+7;
 
int R, C;
 
typedef array<array<int, 200>, 200> T;
 
void CLEAR(T& a){
	for(int i = 0; i < C; i++){
		for(int j = 0; j < C; j++){
			a[i][j] = MOD;
		}
	}
}
 
void updMult(const T& a, const T& b, T& c, int k, pi irange = mp(0, C-1), pi jrange = mp(0, C-1)){
	if(irange.f > irange.s) return;
 
	int i_M = (irange.f+irange.s)/2;
	int best_j = -1;
	for(int j = jrange.f; j <= jrange.s; j++){
		int val = a[i_M][j]+b[j][k];
		if(val < c[i_M][k]){
			best_j = j;
			c[i_M][k] = val;
		}
	}
	assert(best_j != -1);
	updMult(a, b, c, k, mp(irange.f, i_M-1), mp(jrange.f, best_j));
	updMult(a, b, c, k, mp(i_M+1, irange.s), mp(best_j, jrange.s));
}
 
// void mult(const T& a, const T& b, T& c){ // c = a*b, c should be a new variable
// 	CLEAR(c);
// 	for(int i = 0; i < C; i++){
// 		updMult(a, b, c, i);
// 	}
// 	#warning check whether mult is correct
// }
 
int optimal[205][205];
void mult(const T& a, const T& b, T& c){ // c = a*b, c should be a new variable
	CLEAR(c);

	auto updateTrans = [&](int i, int j, int k){
		if(a[i][j]+b[j][k] < c[i][k]){
			c[i][k] = a[i][j]+b[j][k];
			optimal[i][k] = j;
		}
	};


	for(int i = 0; i < C; i++){
		for(int j = 0; j < C; j++){			
			updateTrans(i, j, i);
		}
	}
	for(int dif = 1; dif < C; dif++){
		for(int i = 0; i+dif < C; i++){
			for(int j = optimal[i][i+dif-1]; j <= optimal[i+1][i+dif]; j++){
				updateTrans(i, j, i+dif);
			}
		}
	}

	for(int dif = -1; dif >= -C; dif--){
		for(int i = C-1; i+dif >= 0; i--){
			for(int j = optimal[i-1][i+dif]; j <= optimal[i][i+dif+1]; j++){
				updateTrans(i, j, i+dif);
			}
		}
	}

}

int H[5005][205];
int Hsum[5005][205];
int V[5005][205];
 
const int SZ = 1030; //SZ = 250 --> 10^7
const int K = 10;
T stored[SZ];
int top_pos;
vi trans[SZ];
vi update_poses[5005];
int cur;
bool init_pos[SZ];
 
T buildSmall(int r){
	assert(0 <= r && r < R);
	T res;
	for(int i = 0; i < C; i++){
		for(int j = 0; j < C; j++){
			res[i][j] = abs(Hsum[r][i]-Hsum[r][j])+V[r][j];
		}
	}
	return res;
}
 
void update(int pos){
	assert(sz(trans[pos]));
	if(trans[pos][0] <= 0){ //individual updates
		//remember to negate
		stored[pos] = buildSmall(-trans[pos][0]);
		if(sz(trans[pos]) > 1){
			T ndp;
			for(int i = 1; i < sz(trans[pos]); i++){
				T small = buildSmall(-trans[pos][i]);
				mult(stored[pos], small, ndp);
				swap(ndp, stored[pos]);
			}
		}
		
	}
	else{
		stored[pos] = stored[trans[pos][0]];
		if(sz(trans[pos]) > 1){
			T ndp;
			for(int i = 1; i < sz(trans[pos]); i++){
				mult(stored[pos], stored[trans[pos][i]], ndp);
				swap(ndp, stored[pos]);
			}
		}
	}
}
 
vi initStoredUpdate(int pos){
	assert(sz(trans[pos]));
	init_pos[pos] = 1;
	vi res;
	if(trans[pos][0] <= 0){
		for(auto u: trans[pos]){
			res.pb(-u);
		}
	}
	else{
		for(auto u: trans[pos]){
			if(!init_pos[u]){
				vi add = initStoredUpdate(u);
				for(auto x: add){
					res.pb(x);
				}
			}
		}
	}
 
	update(pos);
	for(auto u: res){
		update_poses[u].pb(pos);
	}
	return res;
}
 
void reBuildHsum(int P){
	Hsum[P][0] = 0;
	for(int i = 1; i < C; i++){
		Hsum[P][i] = Hsum[P][i-1]+H[P][i-1];
	}
}
 
clock_t CL;
 
db getTime(){
	return db(clock()-CL)/db(CLOCKS_PER_SEC);
}
 
// void buildTransitions(){
// 	top_pos = ++cur;
//     for(int i = 0; i < R; i+=K){
//     	int this_pos = ++cur;
//     	assert(cur+5 < SZ);
//     	trans[top_pos].pb(this_pos);
//     	for(int j = i; j < min(R, i+K); j++){
//     		trans[this_pos].pb(-j);
//     	}
//     }
// }
 
int buildTransitions(int lo = 0, int hi = R-1){
	int this_pos = ++cur;
	if(lo == 0 && hi == R-1){
		top_pos = this_pos;
	}
 
	if(hi-lo+1 <= K){
		for(int i = lo; i <= hi; i++){
			trans[this_pos].pb(-i);
		}
	}
	else{
		int M = (lo+hi)/2;
		trans[this_pos].pb(buildTransitions(lo, M));
		trans[this_pos].pb(buildTransitions(M+1, hi));
	}
 
	return this_pos;
}
 
void init(int _R, int _C, int _H[5000][200], int _V[5000][200]) {
	CL = clock();
    for(int i = 0; i < 5005; i++){
    	for(int j = 0; j < 205; j++){
    		H[i][j] = Hsum[i][j] = V[i][j] = 0;
    	}
    }
 
   	top_pos = 0;
   	for(int i = 0; i < SZ; i++){
   		trans[i].clear();
   	}
   	for(int i = 0; i < 5005; i++){
   		update_poses[i].clear();
   	}
   	cur = 0;
   	for(int i = 0; i < SZ; i++){
   		init_pos[i] = 0;
   	}
    #warning clear memory TO 0
   	R = _R;
   	C = _C;
 
   	for(int i = 0; i < R; i++){
   		for(int j = 0; j < C-1; j++){
   			H[i][j] = _H[i][j];
   		}
   	}
 
   	for(int i = 0; i < R-1; i++){
   		for(int j = 0; j < C; j++){
   			V[i][j] = _V[i][j];
   		}
   	}
 
   	for(int i = 0; i < R; i++){
   		reBuildHsum(i);
   	}
    //build transitions
 
    buildTransitions();
    
 
    //cout << "cur: " << cur << "\n";
 
    //#warning assert that SZ is big enough
 
    initStoredUpdate(top_pos);
    //cout << getTime() << "\n";
}
 
 
 
void changeH(int P, int Q, int W) {
    H[P][Q] = W;
 
    reBuildHsum(P);
    
    for(auto u: update_poses[P]){
    	update(u);
    }
   	//cout << getTime() << "\n";
}
 
void changeV(int P, int Q, int W) {
	V[P][Q] = W;
    for(auto u: update_poses[P]){
    	update(u);
    }
    //cout << getTime() << "\n";
}
 
int escape(int V1, int V2) {
	// for(int i = 0; i < R; i++){
	// 	for(int j = 0; j < C; j++){
	// 		cout << i << " " << j << " " << H[i][j] << " " << V[i][j] << "\n";
	// 	}
	// }
    return stored[top_pos][V1][V2];
}

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:232:6: warning: #warning clear memory TO 0 [-Wcpp]
  232 |     #warning clear memory TO 0
      |      ^~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 177592 KB Output is correct
2 Correct 790 ms 177664 KB Output is correct
3 Correct 870 ms 180436 KB Output is correct
4 Correct 778 ms 177604 KB Output is correct
5 Correct 762 ms 177604 KB Output is correct
6 Correct 6 ms 13132 KB Output is correct
7 Correct 6 ms 13128 KB Output is correct
8 Correct 7 ms 13124 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13132 KB Output is correct
2 Correct 8 ms 13012 KB Output is correct
3 Correct 8 ms 13128 KB Output is correct
4 Correct 8 ms 13512 KB Output is correct
5 Correct 8 ms 13388 KB Output is correct
6 Correct 8 ms 13380 KB Output is correct
7 Correct 7 ms 13388 KB Output is correct
8 Correct 8 ms 13388 KB Output is correct
9 Correct 8 ms 13460 KB Output is correct
10 Correct 8 ms 13388 KB Output is correct
11 Correct 85 ms 15844 KB Output is correct
12 Correct 8 ms 13388 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 18268 KB Output is correct
2 Correct 127 ms 18024 KB Output is correct
3 Correct 173 ms 18268 KB Output is correct
4 Correct 179 ms 18144 KB Output is correct
5 Correct 168 ms 18116 KB Output is correct
6 Correct 6 ms 13016 KB Output is correct
7 Correct 6 ms 13004 KB Output is correct
8 Correct 7 ms 13132 KB Output is correct
9 Correct 557 ms 18140 KB Output is correct
10 Correct 7 ms 13132 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 181652 KB Output is correct
2 Correct 779 ms 181536 KB Output is correct
3 Correct 793 ms 181552 KB Output is correct
4 Correct 804 ms 182912 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 18144 KB Output is correct
2 Correct 131 ms 18136 KB Output is correct
3 Correct 180 ms 18124 KB Output is correct
4 Correct 171 ms 18148 KB Output is correct
5 Correct 171 ms 18144 KB Output is correct
6 Correct 769 ms 181552 KB Output is correct
7 Correct 790 ms 181628 KB Output is correct
8 Correct 822 ms 181700 KB Output is correct
9 Correct 807 ms 182920 KB Output is correct
10 Correct 777 ms 177496 KB Output is correct
11 Correct 771 ms 177580 KB Output is correct
12 Correct 842 ms 180368 KB Output is correct
13 Correct 778 ms 177660 KB Output is correct
14 Correct 757 ms 177604 KB Output is correct
15 Correct 6 ms 13108 KB Output is correct
16 Correct 6 ms 13120 KB Output is correct
17 Correct 6 ms 13132 KB Output is correct
18 Correct 8 ms 13388 KB Output is correct
19 Correct 8 ms 13388 KB Output is correct
20 Correct 8 ms 13388 KB Output is correct
21 Correct 8 ms 13388 KB Output is correct
22 Correct 10 ms 13388 KB Output is correct
23 Correct 8 ms 13384 KB Output is correct
24 Correct 9 ms 13388 KB Output is correct
25 Correct 91 ms 15844 KB Output is correct
26 Correct 8 ms 13388 KB Output is correct
27 Correct 559 ms 18204 KB Output is correct
28 Correct 1848 ms 185656 KB Output is correct
29 Correct 2058 ms 183968 KB Output is correct
30 Correct 1977 ms 183996 KB Output is correct
31 Correct 1917 ms 187404 KB Output is correct
32 Correct 7 ms 13132 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 18140 KB Output is correct
2 Correct 133 ms 18136 KB Output is correct
3 Correct 173 ms 18116 KB Output is correct
4 Correct 171 ms 18144 KB Output is correct
5 Correct 171 ms 18116 KB Output is correct
6 Correct 766 ms 181616 KB Output is correct
7 Correct 761 ms 181568 KB Output is correct
8 Correct 776 ms 181680 KB Output is correct
9 Correct 808 ms 182876 KB Output is correct
10 Correct 762 ms 177592 KB Output is correct
11 Correct 783 ms 177628 KB Output is correct
12 Correct 850 ms 180548 KB Output is correct
13 Correct 784 ms 177788 KB Output is correct
14 Correct 756 ms 177648 KB Output is correct
15 Correct 2078 ms 191364 KB Output is correct
16 Correct 6334 ms 192468 KB Output is correct
17 Correct 6 ms 13132 KB Output is correct
18 Correct 7 ms 13132 KB Output is correct
19 Correct 7 ms 13128 KB Output is correct
20 Correct 8 ms 13496 KB Output is correct
21 Correct 8 ms 13388 KB Output is correct
22 Correct 8 ms 13388 KB Output is correct
23 Correct 8 ms 13516 KB Output is correct
24 Correct 8 ms 13476 KB Output is correct
25 Correct 8 ms 13388 KB Output is correct
26 Correct 8 ms 13388 KB Output is correct
27 Correct 84 ms 15768 KB Output is correct
28 Correct 8 ms 13516 KB Output is correct
29 Correct 573 ms 18240 KB Output is correct
30 Correct 1847 ms 185920 KB Output is correct
31 Correct 4976 ms 190056 KB Output is correct
32 Correct 4931 ms 190056 KB Output is correct
33 Correct 2001 ms 184192 KB Output is correct
34 Correct 5539 ms 188012 KB Output is correct
35 Correct 2005 ms 184136 KB Output is correct
36 Correct 5509 ms 187992 KB Output is correct
37 Correct 1896 ms 187440 KB Output is correct
38 Correct 5139 ms 190696 KB Output is correct
39 Correct 7 ms 13100 KB Output is correct
40 Correct 5656 ms 188236 KB Output is correct