Submission #410094

#	Time	Username	Problem	Language	Result	Execution time	Memory
410094		rqi	Wombats (IOI13_wombats)	C++14	76 / 100	20066 ms	187312 KiB

wombats

#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 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 (stderr)

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:52:3: warning: #warning check whether mult is correct [-Wcpp]
   52 |  #warning check whether mult is correct
      |   ^~~~~~~
wombats.cpp:197:6: warning: #warning clear memory TO 0 [-Wcpp]
  197 |     #warning clear memory TO 0
      |      ^~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 24