Submission #100280

#	Time	Username	Problem	Language	Result	Execution time	Memory
100280		Milki	Konj (COCI19_konj)	C++14	70 / 70	129 ms	19424 KiB

konj

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

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int mod = 1e9 + 7, MAXN = 305, inf = 1e9, MAX = 2e5 + 5;

int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
int mul(int x, int y) {return (ll) x * y % mod;}

struct str{
  int x1, y1, x2, y2, id, up;
  str(){}
  str(int x1, int y1, int x2, int y2, int id) : x1(x1), y1(y1), x2(x2), y2(y2), id(id) {
    if(y1 == y2) up = 1;
    else up = 0;
  }
};

int n;
str linije[MAX];
vector <str> row[MAXN], col[MAXN];
vector <int> id[MAXN][MAXN];
int X, Y;
bool bio[MAXN][MAXN];
char c[MAXN][MAXN];

void rek(int x){
  //TRACE(x);
  if(bio[ linije[x].x1 ][ linije[x].y1 ] && bio[ linije[x].x2 ][ linije[x].y2 ]) return;
  bio[linije[x].x1][linije[x].y1] = bio[linije[x].x2][linije[x].y2] = true;

  for(auto it : id[linije[x].x1][linije[x].y1])
    rek(it);
  for(auto it : id[linije[x].x2][linije[x].y2])
    rek(it);
}

void drawRow(int l, int r, int x){
  if(l == -1) return;
  for(int i = l; i <= r; ++i)
    c[x][i] = '#';
}

void drawCol(int l, int r, int x){
  if(l == -1) return;
  for(int i = l; i <= r; ++i)
    c[i][x] = '#';
}

bool cmpRow(str A, str B){
  return A.y1 < B.y1;
}

bool cmpCol(str A, str B){
  return A.x1 < B.x1;
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n;
  REP(i, n){
    int a, b, c, d; cin >> a >> b >> c >> d;
    str A = str(a, b, c, d, i), B = str(c, d, a, b, i);
    id[a][b].pb(i);
    id[c][d].pb(i);

    if(a == c){
      if(b > d) swap(A, B);
      row[a].pb(A);
    }
    if(b == d){
      if(a > c) swap(A, B);
      col[b].pb(A);
    }
    linije[i] = A;
  }
  cin >> X >> Y;
  REP(i, n){
    if(linije[i].up && linije[i].y1 == Y && linije[i].x1 <= X && linije[i].x2 >= X) rek(i);
    else if(!linije[i].up && linije[i].x1 == X && linije[i].y1 <= Y && linije[i].y1 >= Y) rek(i);
  }

  REP(i, MAXN){
    sort(row[i].begin(), row[i].end(), cmpRow);
    sort(col[i].begin(), col[i].end(), cmpCol);

    point curr = point(-1, -1);
    for(auto it : row[i]){
      if(bio[it.x1][it.y1]){
        //TRACE(it.id);
        if(curr.first == -1) curr = point(it.y1, it.y2);
        else if(curr.second >= it.y1) curr.second = max(curr.second, it.y2);
        else { drawRow(curr.first, curr.second, i); curr = point(it.y1, it.y2); }
      }
      else drawRow(curr.first, curr.second, i), curr = point(-1, -1);
    }
    drawRow(curr.first, curr.second, i);
    curr = point(-1, -1);
    for(auto it : col[i]){

      if(bio[it.x1][it.y1]){
        if(curr.first == -1) curr = point(it.x1, it.x2);
        else if(curr.second >= it.x1) curr.second = max(curr.second, it.x2);
        else { drawCol(curr.first, curr.second, i); curr = point(it.x1, it.x2); }
      }
      else drawCol(curr.first, curr.second, i), curr = point(-1, -1);
    }
    drawCol(curr.first, curr.second, i);
  }

  int maxx = 0, maxy = 0, minx = inf, miny = inf;
  REP(i, MAXN) REP(j, MAXN){
    if(c[i][j] == '#'){
      maxx = max(maxx, i); maxy = max(maxy, j);
      minx = min(minx, i); miny = min(miny, j);
    }
    else c[i][j] = '.';
  }

  for(int j = maxy; j >= miny; --j){
    for(int i = minx; i <= maxx; ++i)
      cout << c[i][j];
    cout << "\n";
  }
}

• Subtask 1: 70 / 70