oj.uz

답안 #80433

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
80433 2018-10-20T17:24:58 Z KLPP 자리 배치 (IOI18_seats) C++14
11 / 100
 4000 ms 77060 KB 
#include "seats.h"
#include<iostream>
#include<vector>

using namespace std;
typedef long long int lld;
typedef pair<int,int> pii;
int h,w;
int r[1000010];
int c[1000010];
pii arr[1000010];
//segtree
pii sum[8000000];
pii minimo[8000000];
int counter[8000000];
vector<vector<int> >table;
void update_pos(int a, int b){
	if(a<0 || a>h-1)return;
	if(b<0 || b>w-1)return;
	int t[3][3];
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++)t[i][j]=1;
	}//cout<<a<<" "<<b<<endl;
	t[1][1]=0;
	if(a==0 || b==0 || table[a-1][b-1]>table[a][b])t[0][0]=0;
	if(a==0 || b==w-1 || table[a-1][b+1]>table[a][b])t[0][2]=0;
	if(a==h-1 || b==0 || table[a+1][b-1]>table[a][b])t[2][0]=0;
	if(a==h-1 || b==w-1 || table[a+1][b+1]>table[a][b])t[2][2]=0;
	if(a==0 || table[a-1][b]>table[a][b])t[0][1]=0;
	if(b==0 || table[a][b-1]>table[a][b])t[1][0]=0;
	if(a==h-1 || table[a+1][b]>table[a][b])t[2][1]=0;
	if(b==w-1 || table[a][b+1]>table[a][b])t[1][2]=0;
	/*for(int i=0;i<3;i++){
		for(int j=0;j<3;j++)cout<<t[i][j];
		cout<<endl;
	}cout<<endl;*/
	int x,y,z,w;
	x=t[0][0]+t[0][1]+t[1][0]+t[1][1];
	y=t[1][0]+t[1][1]+t[2][0]+t[2][1];
	z=t[0][1]+t[0][2]+t[1][1]+t[1][2];
	w=t[1][1]+t[1][2]+t[2][1]+t[2][2];
	int cnt[5];
	for(int i=0;i<5;i++)cnt[i]=0;
	cnt[x]++;
	cnt[y]++;
	cnt[z]++;
	cnt[w]++;
	//cout<<table[a][b]<<" "<<x<<endl;
	//cout<<cnt[0]-cnt[1]<<endl;
	arr[table[a][b]].first=cnt[0]-cnt[1];
	arr[table[a][b]].second=cnt[2]-cnt[3];
}
pii Sum(pii a, pii b){
	pii c=pii(a.first+b.first,a.second+b.second);
	return c;
}
pii min(pii a, pii b){
	if(a.second<b.second)return a;
	if(a.second>b.second)return b;
	if(a.first>b.first)return b;
	return a;
}
void build(int a, int b, int node){
	if(a==b){
		sum[node]=arr[a];
		minimo[node]=arr[a];
		counter[node]=1;
		return;
	}
	int mid=(a+b)/2;
	build(a,mid,2*node);
	build(mid+1,b,2*node+1);
	sum[node]=Sum(sum[2*node],sum[2*node+1]);
	minimo[node]=min(minimo[2*node],Sum(minimo[2*node+1],sum[2*node]));
	counter[node]=0;
	if(minimo[node]==minimo[2*node]){
		counter[node]+=counter[2*node];
	}
	if(minimo[node]==Sum(minimo[2*node+1],sum[2*node])){
		counter[node]+=counter[2*node+1];
	}
}
void update(int a, int b, int node, int pos){
	if(pos<a || b<pos)return;
	if(a==b){
		sum[node]=arr[a];
		minimo[node]=arr[a];
		counter[node]=1;
		return;
	}
	int mid=(a+b)/2;
	update(a,mid,2*node,pos);
	update(mid+1,b,2*node+1,pos);
	sum[node]=Sum(sum[2*node],sum[2*node+1]);
	minimo[node]=min(minimo[2*node],Sum(minimo[2*node+1],sum[2*node]));
	counter[node]=0;
	if(minimo[node]==minimo[2*node]){
		counter[node]+=counter[2*node];
	}
	if(minimo[node]==Sum(minimo[2*node+1],sum[2*node])){
		counter[node]+=counter[2*node+1];
	}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	h=H;
	w=W;
	for(int i=0;i<h;i++){
		vector<int> a;
		for(int j=0;j<w;j++)a.push_back(-1);
		table.push_back(a);
	}
	for(int i=0;i<w*h;i++){
		r[i]=R[i];
		c[i]=C[i];
		table[R[i]][C[i]]=i;
	}
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++)update_pos(i,j);
	}
	build(0,w*h-1,1);
	//for(int i=0;i<h*w;i++)cout<<arr[i].second<<endl;
	//cout<<counter[1]<<endl;
}

int swap_seats(int a, int b) {
	swap(table[r[a]][c[a]],table[r[b]][c[b]]);
	swap(r[a],r[b]);
	swap(c[a],c[b]);
	for(int i=-1;i<2;i++){
		for(int j=-1;j<2;j++){
			update_pos(r[a]+i,c[a]+j);
			if(r[a]+i>=0 && r[a]+i<=h-1 && c[a]+j>=0 && c[a]+j<=w-1)update(0,h*w-1,1,table[r[a]+i][c[a]+j]);
			update_pos(r[b]+i,c[b]+j);
			if(r[b]+i>=0 && r[b]+i<=h-1 && c[b]+j>=0 && c[b]+j<=w-1)update(0,h*w-1,1,table[r[b]+i][c[b]+j]);
		}
	}
	build(0,h*w-1,1);
	/*int cnt=0;
	int one=0;
	int three=0;
	for(int i=0;i<h*w;i++){
		three+=arr[i].second;
		one+=arr[i].first;
		if(one==4 && three==0){
			cnt++;
		}
	}*/
	return counter[1];
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 508 KB Output is correct
2 Correct 18 ms 628 KB Output is correct
3 Correct 28 ms 628 KB Output is correct
4 Correct 17 ms 628 KB Output is correct
5 Correct 26 ms 656 KB Output is correct
6 Correct 26 ms 740 KB Output is correct
7 Correct 26 ms 804 KB Output is correct
8 Correct 26 ms 804 KB Output is correct
9 Correct 26 ms 804 KB Output is correct
10 Correct 31 ms 804 KB Output is correct
11 Correct 24 ms 804 KB Output is correct
12 Correct 16 ms 804 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 508 KB Output is correct
2 Correct 18 ms 628 KB Output is correct
3 Correct 28 ms 628 KB Output is correct
4 Correct 17 ms 628 KB Output is correct
5 Correct 26 ms 656 KB Output is correct
6 Correct 26 ms 740 KB Output is correct
7 Correct 26 ms 804 KB Output is correct
8 Correct 26 ms 804 KB Output is correct
9 Correct 26 ms 804 KB Output is correct
10 Correct 31 ms 804 KB Output is correct
11 Correct 24 ms 804 KB Output is correct
12 Correct 16 ms 804 KB Output is correct
13 Correct 1185 ms 1716 KB Output is correct
14 Correct 1196 ms 1808 KB Output is correct
15 Correct 994 ms 1808 KB Output is correct
16 Correct 781 ms 2236 KB Output is correct
17 Correct 1062 ms 2236 KB Output is correct
18 Correct 805 ms 2236 KB Output is correct
19 Correct 798 ms 2236 KB Output is correct
20 Correct 789 ms 2236 KB Output is correct
21 Correct 811 ms 2236 KB Output is correct
22 Correct 763 ms 2296 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1092 ms 77060 KB Output is correct
2 Execution timed out 4034 ms 77060 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 77060 KB Output is correct
2 Correct 65 ms 77060 KB Output is correct
3 Correct 138 ms 77060 KB Output is correct
4 Correct 749 ms 77060 KB Output is correct
5 Execution timed out 4014 ms 77060 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 508 KB Output is correct
2 Correct 18 ms 628 KB Output is correct
3 Correct 28 ms 628 KB Output is correct
4 Correct 17 ms 628 KB Output is correct
5 Correct 26 ms 656 KB Output is correct
6 Correct 26 ms 740 KB Output is correct
7 Correct 26 ms 804 KB Output is correct
8 Correct 26 ms 804 KB Output is correct
9 Correct 26 ms 804 KB Output is correct
10 Correct 31 ms 804 KB Output is correct
11 Correct 24 ms 804 KB Output is correct
12 Correct 16 ms 804 KB Output is correct
13 Correct 1185 ms 1716 KB Output is correct
14 Correct 1196 ms 1808 KB Output is correct
15 Correct 994 ms 1808 KB Output is correct
16 Correct 781 ms 2236 KB Output is correct
17 Correct 1062 ms 2236 KB Output is correct
18 Correct 805 ms 2236 KB Output is correct
19 Correct 798 ms 2236 KB Output is correct
20 Correct 789 ms 2236 KB Output is correct
21 Correct 811 ms 2236 KB Output is correct
22 Correct 763 ms 2296 KB Output is correct
23 Execution timed out 4035 ms 77060 KB Time limit exceeded
24 Halted 0 ms 0 KB -