제출 #1245666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1245666		santi3223	자리 배치 (IOI18_seats)	C++20	0 / 100	4094 ms	327680 KiB

seats

#include <bits/stdc++.h>
//#include "horses.h"
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(int aa = bb; aa < cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;

set<pair<pll, pll>> st;
vector<vl> grid;
map<ll, pll> pos;
ll h, w;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C){
	h = H;
	w = W;
	grid = vector<vl>(H, vl(W));
	ff(i, 0, H*W){
		pos[i] = {R[i], C[i]};
		grid[R[i]][C[i]] = i;
	}
}

ll c = 0;

void cases(pll ti, pll bd, set<ll> seats, ll orient){
	//cout << ti.fi << " " << ti.se << "   " << bd.fi << " " << bd.se << ed;
	if(ti.fi < 0 || ti.se < 0 || bd.fi >= h || bd.se >= w){
		//cout << "OUT" << ed;
		return;
	}
	if(orient == 0){
		//cout << "BASE" << ed;
		seats.insert(0);
	}
	else{
		//cout << "AAAAA" << ed;
		ll sz = st.size();
		//cout << "AAAAA" << ed;
		st.insert({ti, bd});
		//cout << "AAAAA" << ed;
		//cout << st.size() << "  " << sz << ed;
		if(st.size() == sz){
			//cout << "TRASH" << ed;
			return;
		}
		//cout << "AFTER" << ed;
	}
	//{y, x}
	pll td = {ti.fi, bd.se}, bi = {bd.fi, ti.se}; 
	//cout << "CHECK " << orient << ed;
	//cout << ti.fi << " " <<ti.se << "   " << bd.fi << " " << bd.se << ed;
	if(orient == 1){
	//	cout << "C1" << " ";
		ff(i, ti.fi, bi.fi+1){
			seats.insert(grid[i][ti.se]);
		}
	}
	else if(orient == 2){
		//cout << "C2" << " ";
		ff(i, td.fi, bd.fi+1){
			seats.insert(grid[i][td.se]);
		}
	}
	else if(orient == 3){
		//cout << "C3" << " ";
		ff(i, ti.se, td.se+1){
			seats.insert(grid[ti.fi][i]);
		}
	}
	else if(orient == 4){
		//cout << "C4" << " ";
		ff(i, bi.se, bd.se+1){
			seats.insert(grid[bi.fi][i]);
		}
	}
	if(seats.size()-1 == *seats.rbegin()){
		//cout << "PLUS" << ed;
		c++;
	}
	//cout << ed;
	set<ll> s = seats;
	cases({ti.fi, ti.se-1}, bd, s, 1);
	s = seats;
	cases(ti, {bd.fi, bd.se+1}, s, 2);
	s = seats;
	cases({ti.fi-1, ti.se}, bd, s, 3);
	s = seats;
	cases(ti, {bd.fi+1, bd.se}, s, 4);
}

int swap_seats(int a, int b){
	st.clear();
	ll x1 = pos[a].se, y1 = pos[a].fi, x2 = pos[b].se, y2 = pos[b].fi;
	swap(grid[y1][x1], grid[y2][x2]);
	swap(pos[a], pos[b]);
	ll stx = pos[0].se, sty = pos[0].fi;
	pll coords = pos[0];
	c = 0;
	set<ll> s;
	cases(coords, coords, s, 0);
	return c;
}
/*

namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int H = read_int();
  int W = read_int();
  int Q = read_int();
  std::vector<int> R(H * W), C(H * W);
  for (int i = 0; i < H * W; ++i) {
    R[i] = read_int();
    C[i] = read_int();
  }
  std::vector<int> A(Q), B(Q);
  for (int j = 0; j < Q; ++j) {
    A[j] = read_int();
    B[j] = read_int();
  }

  give_initial_chart(H, W, R, C);
  for (int j = 0; j < Q; ++j) {
    int answer = swap_seats(A[j], B[j]);
    printf("%d\n", answer);
  }
  return 0;
}
*/

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