oj.uz

답안 #76494

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
76494 2018-09-13T20:31:54 Z Xellos 자리 배치 (IOI18_seats) C++14
11 / 100
 4000 ms 134140 KB 
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;

int R, C;
vector< vector<int> > table;
vector<int> pos_R, pos_C;
vector< set<int> > row_lst;
vector<int> rowmin_top, rowmin_bot;
vector<int> sdiv;
vector< vector<int> > group_min, group_max;
vector<int> group1000_min, group1000_max;

void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
	if(H > W) {
		swap(H, W);
		swap(r, c);
	}
	R = H;
	C = W;
	pos_R = r, pos_C = c;
	table.resize(R, vector<int>(C));
	for(int i = 0; i < H*W; i++) table[r[i]][c[i]] = i;
	row_lst.resize(R);
	for(int i = 0; i < H*W; i++) row_lst[r[i]].insert(i);
	rowmin_top.resize(R+1, R*C);
	rowmin_bot.resize(R+1, R*C);
	sdiv.resize(R, 0);
	for(int i = 0; i < R; i++)
		for(int j = 2; j*j <= i+1; j++) if((i+1)%j == 0) sdiv[i] = j-1;
	group_min.resize(R);
	group_max.resize(R);
	for(int i = 0; i < R; i++) {
		group_min[i].resize(R*C/(i+1), C);
		group_max[i].resize(R*C/(i+1), 0);
		for(int j = 0; j < R*C/(i+1); j++) {
			if(sdiv[i]) for(int k = 0; k < (i+1)/(sdiv[i]+1); k++) {
				group_min[i][j] = min(group_min[i][j], group_min[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
				group_max[i][j] = max(group_max[i][j], group_max[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
			}
			else if(i < 15) for(int k = 0; k < i+1; k++) {
				group_min[i][j] = min(group_min[i][j], pos_C[j*(i+1)+k]);
				group_max[i][j] = max(group_max[i][j], pos_C[j*(i+1)+k]);
			}
			else {
				int cur = j*(i+1);
				while(cur%13 != 0) {
					group_min[i][j] = min(group_min[i][j], pos_C[cur]);
					group_max[i][j] = max(group_max[i][j], pos_C[cur]);
					cur++;
				}
				while(cur+13 <= (j+1)*(i+1)) {
					group_min[i][j] = min(group_min[i][j], group_min[12][cur/13]);
					group_max[i][j] = max(group_max[i][j], group_max[12][cur/13]);
					cur += 13;
				}
				while(cur < (j+1)*(i+1)) {
					group_min[i][j] = min(group_min[i][j], pos_C[cur]);
					group_max[i][j] = max(group_max[i][j], pos_C[cur]);
					cur++;
				}
			}
		}
	}
	group1000_min.resize(R*C/1000, C);
	group1000_max.resize(R*C/1000, 0);
	for(int i = 0; i < R*C/1000; i++) for(int j = 0; j < 1000; j++) {
		group1000_min[i] = min(group1000_min[i], pos_C[i*1000+j]);
		group1000_max[i] = max(group1000_max[i], pos_C[i*1000+j]);
	}
}

int swap_seats(int a, int b) {
	// if(C > 10000) return 0;
	row_lst[pos_R[a]].erase(a);
	row_lst[pos_R[b]].erase(b);
	swap(table[pos_R[a]][pos_C[a]], table[pos_R[b]][pos_C[b]]);
	swap(pos_R[a], pos_R[b]);
	swap(pos_C[a], pos_C[b]);
	row_lst[pos_R[a]].insert(a);
	row_lst[pos_R[b]].insert(b);
	for(int i = 0; i < R; i++) if(a/(i+1) < R*C/(i+1)) {
		group_min[i][a/(i+1)] = C;
		group_max[i][a/(i+1)] = 0;
		int j = a/(i+1);
		if(sdiv[i]) for(int k = 0; k < (i+1)/(sdiv[i]+1); k++) {
			group_min[i][j] = min(group_min[i][j], group_min[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
			group_max[i][j] = max(group_max[i][j], group_max[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
		}
		else if(i < 15) for(int k = 0; k < i+1; k++) {
			group_min[i][j] = min(group_min[i][j], pos_C[j*(i+1)+k]);
			group_max[i][j] = max(group_max[i][j], pos_C[j*(i+1)+k]);
		}
		else {
			int cur = j*(i+1);
			while(cur%13 != 0) {
				group_min[i][j] = min(group_min[i][j], pos_C[cur]);
				group_max[i][j] = max(group_max[i][j], pos_C[cur]);
				cur++;
			}
			while(cur+13 <= (j+1)*(i+1)) {
				group_min[i][j] = min(group_min[i][j], group_min[12][cur/13]);
				group_max[i][j] = max(group_max[i][j], group_max[12][cur/13]);
				cur += 13;
			}
			while(cur < (j+1)*(i+1)) {
				group_min[i][j] = min(group_min[i][j], pos_C[cur]);
				group_max[i][j] = max(group_max[i][j], pos_C[cur]);
				cur++;
			}
		}
	}
	for(int i = 0; i < R; i++) if(b/(i+1) < R*C/(i+1)) {
		group_min[i][b/(i+1)] = C;
		group_max[i][b/(i+1)] = 0;
		int j = b/(i+1);
		if(sdiv[i]) for(int k = 0; k < (i+1)/(sdiv[i]+1); k++) {
			group_min[i][j] = min(group_min[i][j], group_min[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
			group_max[i][j] = max(group_max[i][j], group_max[sdiv[i]][j*((i+1)/(sdiv[i]+1))+k]);
		}
		else if(i < 15) for(int k = 0; k < i+1; k++) {
			group_min[i][j] = min(group_min[i][j], pos_C[j*(i+1)+k]);
			group_max[i][j] = max(group_max[i][j], pos_C[j*(i+1)+k]);
		}
		else {
			int cur = j*(i+1);
			while(cur%13 != 0) {
				group_min[i][j] = min(group_min[i][j], pos_C[cur]);
				group_max[i][j] = max(group_max[i][j], pos_C[cur]);
				cur++;
			}
			while(cur+13 <= (j+1)*(i+1)) {
				group_min[i][j] = min(group_min[i][j], group_min[12][cur/13]);
				group_max[i][j] = max(group_max[i][j], group_max[12][cur/13]);
				cur += 13;
			}
			while(cur < (j+1)*(i+1)) {
				group_min[i][j] = min(group_min[i][j], pos_C[cur]);
				group_max[i][j] = max(group_max[i][j], pos_C[cur]);
				cur++;
			}
		}
	}
	if(a/1000 < R*C/1000) {
		group1000_min[a/1000] = C;
		group1000_max[a/1000] = 0;
		for(int j = 0; j < 1000; j++) {
			group1000_min[a/1000] = min(group1000_min[a/1000], pos_C[(a/1000)*1000+j]);
			group1000_max[a/1000] = max(group1000_max[a/1000], pos_C[(a/1000)*1000+j]);
		}
	}
	if(b/1000 < R*C/1000) {
		group1000_min[b/1000] = C;
		group1000_max[b/1000] = 0;
		for(int j = 0; j < 1000; j++) {
			group1000_min[b/1000] = min(group1000_min[b/1000], pos_C[(b/1000)*1000+j]);
			group1000_max[b/1000] = max(group1000_max[b/1000], pos_C[(b/1000)*1000+j]);
		}
	}
	int ans = 0, cur_max = 0;
	int rl = pos_R[0], rr = pos_R[0], cl = pos_C[0], cr = pos_C[0];
	for(int i = 0; i < pos_R[0]; i++) rowmin_top[i+1] = min(rowmin_top[i], *begin(row_lst[i]));
	for(int i = R-1; i >= pos_R[0]; i--) rowmin_bot[i] = min(rowmin_bot[i+1], *begin(row_lst[i]));
	for(int i = 0; i < R; i++) {
		int cur_out_min = min(rowmin_bot[rr+1], rowmin_top[rl]);
		int D = cur_max / (rr-rl+1);
		cl = min(cl, group_min[rr-rl][D]);
		cr = max(cr, group_max[rr-rl][D]);
		cur_max = (D+1) * (rr-rl+1) - 1;
		while((rr-rl+1)*(cr-cl+1) <= cur_out_min) {
			if((rr-rl+1)*(cr-cl+1) == cur_max+1) ans++;
			D++;
			if(cur_max+rr-rl+1 >= cur_out_min) break;
			cur_max += rr-rl+1;
			if(D < R*C/(rr-rl+1)) {
				cl = min(cl, group_min[rr-rl][D]);
				cr = max(cr, group_max[rr-rl][D]);
			}
		}
		if(i == R-1) break;
		int min_top = (rl == 0)   ? R*C : *begin(row_lst[rl-1]);
		int min_bot = (rr == R-1) ? R*C : *begin(row_lst[rr+1]);
		if(min_top < min_bot) rl--;
		else rr++;
	}
	return ans;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 8 ms 620 KB Output is correct
3 Correct 18 ms 652 KB Output is correct
4 Correct 10 ms 652 KB Output is correct
5 Correct 9 ms 652 KB Output is correct
6 Correct 9 ms 652 KB Output is correct
7 Correct 8 ms 680 KB Output is correct
8 Correct 9 ms 680 KB Output is correct
9 Correct 9 ms 760 KB Output is correct
10 Correct 8 ms 760 KB Output is correct
11 Correct 8 ms 760 KB Output is correct
12 Correct 10 ms 760 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 8 ms 620 KB Output is correct
3 Correct 18 ms 652 KB Output is correct
4 Correct 10 ms 652 KB Output is correct
5 Correct 9 ms 652 KB Output is correct
6 Correct 9 ms 652 KB Output is correct
7 Correct 8 ms 680 KB Output is correct
8 Correct 9 ms 680 KB Output is correct
9 Correct 9 ms 760 KB Output is correct
10 Correct 8 ms 760 KB Output is correct
11 Correct 8 ms 760 KB Output is correct
12 Correct 10 ms 760 KB Output is correct
13 Correct 272 ms 1924 KB Output is correct
14 Correct 230 ms 1924 KB Output is correct
15 Correct 396 ms 1924 KB Output is correct
16 Correct 382 ms 1924 KB Output is correct
17 Correct 224 ms 1924 KB Output is correct
18 Correct 133 ms 1924 KB Output is correct
19 Correct 111 ms 1924 KB Output is correct
20 Correct 222 ms 1924 KB Output is correct
21 Correct 384 ms 1924 KB Output is correct
22 Correct 377 ms 1924 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4051 ms 134000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 231 ms 134000 KB Output is correct
2 Correct 1127 ms 134000 KB Output is correct
3 Execution timed out 4037 ms 134140 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 134140 KB Output is correct
2 Correct 67 ms 134140 KB Output is correct
3 Correct 79 ms 134140 KB Output is correct
4 Correct 911 ms 134140 KB Output is correct
5 Correct 3707 ms 134140 KB Output is correct
6 Execution timed out 4053 ms 134140 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 8 ms 620 KB Output is correct
3 Correct 18 ms 652 KB Output is correct
4 Correct 10 ms 652 KB Output is correct
5 Correct 9 ms 652 KB Output is correct
6 Correct 9 ms 652 KB Output is correct
7 Correct 8 ms 680 KB Output is correct
8 Correct 9 ms 680 KB Output is correct
9 Correct 9 ms 760 KB Output is correct
10 Correct 8 ms 760 KB Output is correct
11 Correct 8 ms 760 KB Output is correct
12 Correct 10 ms 760 KB Output is correct
13 Correct 272 ms 1924 KB Output is correct
14 Correct 230 ms 1924 KB Output is correct
15 Correct 396 ms 1924 KB Output is correct
16 Correct 382 ms 1924 KB Output is correct
17 Correct 224 ms 1924 KB Output is correct
18 Correct 133 ms 1924 KB Output is correct
19 Correct 111 ms 1924 KB Output is correct
20 Correct 222 ms 1924 KB Output is correct
21 Correct 384 ms 1924 KB Output is correct
22 Correct 377 ms 1924 KB Output is correct
23 Execution timed out 4051 ms 134000 KB Time limit exceeded
24 Halted 0 ms 0 KB -