Submission #295550

#	Time	Username	Problem	Language	Result	Execution time	Memory
295550		eohomegrownapps	Seats (IOI18_seats)	C++17	0 / 100	4056 ms	117852 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> r;
vector<int> c;
vector<set<int>> firstindr;
vector<set<int>> firstindc;
int h;
int w;

int n;
int INF = 1e9;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	r=R;
	c=C;
	n=H*W;
	h=H;w=W;
	firstindr.resize(h);
	firstindc.resize(w);
	for (int i = 0; i<n; i++){
		firstindr[r[i]].insert(i);
		firstindc[c[i]].insert(i);
	}
	//display(minr);display(maxr);
	//display(minc);display(maxc);
	for (int i = 0; i<h; i++){
		cout<<*firstindr[i].begin()<<' ';
	}cout<<'\n';

	for (int i = 0; i<w; i++){
		cout<<*firstindc[i].begin()<<' ';
	}cout<<'\n';
}

int swap_seats(int a, int b) {
	//cout<<a<<' '<<b<<' '<<r[a]<<' '<<r[b]<<'\n';
	if (r[a]!=r[b]){
		firstindr[r[a]].erase(a);
		firstindr[r[a]].insert(b);
		firstindr[r[b]].erase(b);
		firstindr[r[b]].insert(a);
	}

	if (c[a]!=c[b]){
		firstindc[c[a]].erase(a);
		firstindc[c[a]].insert(b);
		firstindc[c[b]].erase(b);
		firstindc[c[b]].insert(a);
	}

	/*for (int i = 0; i<h; i++){
		cout<<*firstindr[i].begin()<<' ';
	}cout<<'\n';

	for (int i = 0; i<w; i++){
		cout<<*firstindc[i].begin()<<' ';
	}cout<<'\n';*/

	swap(r[a],r[b]);
	swap(c[a],c[b]);

	int zrloc = -1;
	int zcloc = -1;
	for (int i = 0; i<h; i++){
		if (*firstindr[i].begin()==0){
			zrloc=i;break;
		}
	}
	for (int i = 0; i<w; i++){
		if (*firstindc[i].begin()==0){
			zcloc=i;break;
		}
	}
	//cout<<zrloc<<' '<<zcloc<<'\n';
	vector<pair<int,pair<int,int>>> sortarr; // {index, {{rmin,rmax,cmin,cmax},value}}
	int prevind = -1;
	for (int i = zrloc; i<h; i++){
		auto iloc = firstindr[i].upper_bound(prevind);
		if (iloc!=firstindr[i].end()){
			prevind=*iloc;
			sortarr.push_back({*iloc,{1,i}});
		}
	}
	prevind = -1;
	for (int i = zrloc; i>=0; i--){
		auto iloc = firstindr[i].upper_bound(prevind);
		if (iloc!=firstindr[i].end()){
			prevind=*iloc;
			sortarr.push_back({*iloc,{0,i}});
		}
	}

	prevind = -1;
	for (int i = zcloc; i<w; i++){
		auto iloc = firstindc[i].upper_bound(prevind);
		if (iloc!=firstindc[i].end()){
			prevind=*iloc;
			sortarr.push_back({*iloc,{3,i}});
		}
	}
	prevind = -1;
	for (int i = zcloc; i>=0; i--){
		auto iloc = firstindc[i].upper_bound(prevind);
		if (iloc!=firstindc[i].end()){
			prevind=*iloc;
			sortarr.push_back({*iloc,{2,i}});
		}
	}
	sortarr.push_back({n,{-1,-1}});
	sort(sortarr.begin(),sortarr.end());

	int curind = sortarr[0].first;
	int rmin = INF;
	int rmax = -INF;
	int cmin = INF;
	int cmax = -INF;

	int tot = 0;

	for (int i = 0; i<sortarr.size(); i++){
		auto p = sortarr[i];
		//cout<<p.first<<' '<<p.second.first<<' '<<p.second.second<<'\n';
		if (p.first!=curind){
			//cout<<"at "<<curind<<": rmin "<<rmin<<" rmax "<<rmax<<" cmin "<<cmin<<" cmax "<<cmax<<'\n';
			int nextind = sortarr[i].first;
			int totval = (rmax-rmin+1)*(cmax-cmin+1);
			// does totval apply between curind+1 and nextind+1?
			if (curind+1<=totval&&totval<=nextind+1){
				tot++;
			}
			curind=p.first;
		}
		if (p.second.first==-1){break;}
		if (p.second.first==0){
			rmin=min(rmin,p.second.second);
		} else if (p.second.first==1){
			rmax=max(rmax,p.second.second);
		} else if (p.second.first==2){
			cmin=min(cmin,p.second.second);
		} else if (p.second.first==3){
			cmax=max(cmax,p.second.second);
		} else {
			assert(1==0);
		}
	}

  	return tot;
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:122:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |  for (int i = 0; i<sortarr.size(); i++){
      |                  ~^~~~~~~~~~~~~~~

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