Submission #139760

#	Time	Username	Problem	Language	Result	Execution time	Memory
139760		almogwald	Seats (IOI18_seats)	C++14	31 / 100	4018 ms	38772 KiB

seats

#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <iostream>

#include "seats.h"
#define fori(i,n) for(int i=0;i<n;i++)
#define forn(i,n) for(int i=1;i<n;i++)
#define forib(i,n) for(int i=n-1;i>=0;i--)
#define fornb(i,n) for(int i=n-1;i>0;i--)
#define maxl 10000000000
#define con continue;
typedef long long lol;
using namespace std;
typedef vector<int> veci;
typedef pair<lol,lol> point;
lol sum=0;

vector<int> r,c;
vector<veci> all;
veci minr,minc;
int h,w;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  r = R;
  c = C;
  h=H;
  w=W;
  all.resize(H);
  fori(i,H){
	  all[i].resize(W);
  }
  fori(i,h*w){
	  all[r[i]][c[i]]=i;
  }
  minr.resize(H);
  fori(i,H){
	  int mini=h*w;
	  fori(j,w){
		  mini=min(mini,all[i][j]);
	  }
	  minr[i]=mini;
  }
  minc.resize(w);
  fori(j,w){

		int mini=h*w;
		fori(i,H){
			mini=min(mini,all[i][j]);
		}
		minc[j]=mini;
	}
}
int calculate(){
	int sum=1;
	int R=r[0];
	int C=c[0];
	int rows=1,cols=1;
	veci rr;
	int minn=h*w;
	fori(i,R){
		minn=min(minn,minr[i]);
		rr.push_back(minn);
	}
	 minn=h*w;
	forib(i,h){
		if(i==R){
			break;
		}
		minn=min(minn,minr[i]);
		rr.push_back(minn);
	}
	veci cc;
	minn=h*w;
	fori(i,C){
		minn=min(minn,minc[i]);
		cc.push_back(minn);
	}
	 minn=h*w;
	forib(i,w){
		if(i==C){
			break;
		}
		minn=min(minn,minc[i]);
		cc.push_back(minn);
	}
	sort(rr.begin(),rr.end());
	sort(cc.begin(),cc.end());
	int i=0,j=0;
	while(i<h-1 && j<w-1){
		if(rows*cols<=rr[i] && rows*cols<=cc[j]){
			sum++;
		}
		if(rr[i]<cc[j]){
			rows++;
			i++;
		}else{
			cols++;
			j++;
		}
	}
	while(i<h-1){
		if(rows*cols<=rr[i]){
			sum++;
		}
		rows++;
		i++;
	}
	while(j<w-1){
		if(rows*cols<=cc[j]){
			sum++;
		}
		cols++;
		j++;
	}

	return sum;
}
int swap_seats(int a, int b) {
	swap(c[a],c[b]);
	swap(r[a],r[b]);
	swap(all[r[a]][c[a]],all[r[b]][c[b]]);
	int i=r[a];
	int mini=h*w;
	fori(j,w){
	  mini=min(mini,all[i][j]);
	}
	minr[i]=mini;
	i=r[b];
	mini=h*w;
	fori(j,w){
	  mini=min(mini,all[i][j]);
	}
	minr[i]=mini;
	int j=c[a];
	mini=h*w;
	fori(i,h){
		mini=min(mini,all[i][j]);
	}
	minc[j]=mini;
	j=c[b];
	mini=h*w;
	fori(i,h){
		mini=min(mini,all[i][j]);
	}
	minc[j]=mini;
	return calculate();
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30