Submission #293891

#	Time	Username	Problem	Language	Result	Execution time	Memory
293891		ASDF123	Nowruz (IOI17_nowruz)	Text	0 / 100	0 ms	0 KiB

nowruz1.out

#include <bits/stdc++.h>
#include <chrono>
#include <random>

#define pii pair<int, int>
#define fr first
#define sc second
#define szof(s) (int)s.size()

using namespace std;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = (int)1e5 + 5;

char C[1025][1025];
char ANS[1025][1025];

int N, M, K;
double BEST;

struct Struct {
  int i, j, sz;
  Struct () {
    i = j = -1;
    sz = -1e9;
  }
}need;

int get_rand() {
  int x = rnd();
  if (x < 0) {
    x = -x;
  }
  return x;
}

int toy[4] = {-1, 0, 1, 0};
int tox[4] = {0, 1, 0, -1};
int n, m, k;

char c[1025][1025];
int color[1025][1025];
int sz[(int)1e6 * 2];
int ourColor;

bool in_rectangle(int i, int j) {
  return (i >= 1 && i <= n && j >= 1 && j <= m);
}

int kek = 0;

void dfs(int i, int j, int col) {
  //cout << "# " << i << " " << j << endl;
  kek++;
  
  bool flag = (i == 14 && j == 131);
  
  if (kek >= 25000) {
    puts("ok");
    cout << i << " " << j << endl;
    cout << "kek " << kek << endl;
  }
  
  color[i][j] = col;
  sz[col]++;
  
  for (int k = 0; k < 4; k++) {
    int ii = i + toy[k];
    int jj = j + tox[k];
    if (!in_rectangle(ii, jj)) {
      continue;
    }
    
    if (flag) {
      cout << "wtf " << ii << " " << jj << endl; 
      cout << c[ii][jj] << endl;
      cout << color[ii][jj] << endl;
      
      while (1) {
        int x; cin >> x;
      }
      
    }
    if (c[ii][jj] == '.' && color[ii][jj] == -1) {
      dfs(ii, jj, col);
    }
    if (flag) {
      puts("wtf2");
    }
  }
}

bool us[1025][1025];

void check_cycle(int y, int x, int py, int px) {
  us[y][x] = 1;
  for (int k = 0; k < 4; k++) {
    int ny = y + toy[k];
    int nx = x + tox[k];
    if (!in_rectangle(ny, nx)) {
      continue;
    }
    if (c[ny][nx] == '#' || c[ny][nx] == 'X') {
      continue;
    }
    if (ny == py && nx == px) {
      continue;
    }
    if (!us[ny][nx]) {
      check_cycle(ny, nx, y, x);
    } else {
      puts("CYCLE");
      exit(0);
    }
  }
}

bool used[1025][1025]; // 1 our tree

bool check(int y, int x, int py, int px) {
  for (int k = 0; k < 4; k++) {
    int ny = y + toy[k];
    int nx = x + tox[k];
    if (!in_rectangle(ny, nx)) {
      continue;
    }
    if (ny == py && nx == px) {
      continue;
    }
    if (c[ny][nx] == '.') {
      return false;
    }
  }
  return true;
}

void bfs(int sy, int sx) {
  queue <pii> q;
  q.push({sy, sx}); 
  c[sy][sx] = '.';
  used[sy][sx] = 1;
  while (!q.empty()) {
    int y = q.front().fr;
    int x = q.front().sc;
    q.pop();
    for (int k = 0; k < 4; k++) {
      int ny = y + toy[k];
      int nx = x + tox[k];
      if (!in_rectangle(ny, nx)) {
        continue;
      }
      if (check(ny, nx, y, x)) {
        c[ny][nx] = '.';
        used[ny][nx] = 1;
        q.push({ny, nx});
      }
    }
  }
}

inline void solve() {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (c[i][j] == '.') {
        c[i][j] = 'X';
      }
    }
  }
  vector <pii> ourPos;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (color[i][j] == ourColor) {
        ourPos.push_back({i, j});
      }
    }
  }
  int root = get_rand() % szof(ourPos);
  int sy = ourPos[root].fr;
  int sx = ourPos[root].sc;
  
  bfs(sy, sx);
  //puts("answer:");
  //for (int i = 1; i <= n; i++) {
    //for (int j = 1; j <= m; j++) {
      //cout << c[i][j];
    //}cout << endl;
  //}
  check_cycle(ourPos[root].fr, ourPos[root].sc, -1, -1);
}

void init() {
  n = N, m = M, k = K;
  memset (color, -1, sizeof(color));
  memset (sz, 0, sizeof(sz));
  memset (us, 0, sizeof(us));
  memset (used, 0, sizeof(used));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      c[i][j] = C[i][j];
    }
  }
}
void SOLVE() {
  int id = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (c[i][j] == '.' && color[i][j] == -1) {
        cout << "! " << i << " " << j << endl;
        dfs(i, j, id);
        if (sz[id] > need.sz) {
          need.sz = sz[id];
          need.i = i;
          need.j = j;
          ourColor = id;
        }
        id++;
      }
    }
  }
  
  solve();
  
  int good = 0;
  for (int y = 1; y <= n; y++) {
    for (int x = 1; x <= m; x++) {
      if (c[y][x] == '.') {
        int free = 0;
        for (int k = 0; k < 4; k++) {
          int ny = y + toy[k];
          int nx = x + tox[k];
          if (!in_rectangle(ny, nx)) {
            continue;
          }
          free += (c[ny][nx] == '.');
        }
        if (free == 1) {
          good++;
        }
      }
    }
  }
  //cout << "my answer: " << good << endl;
  //cout << "k: " << k << endl;
  //cout << "score: " << min(10.0, 10.0 * delta) << endl;
  
  double delta = (double)good / (double)k;
  double score = min(10.0, 10.0 * delta);
  if (score > BEST) {
    BEST = score;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        ANS[i][j] = c[i][j];
      }
    }
  } 
}

signed main() {
  freopen("tin.txt", "r", stdin);
  
  cin >> N >> M >> K;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      cin >> C[i][j];
      assert(C[i][j] == '.');
    }
  }  
  
  
  for (int xod = 1; xod <= 1; xod++) {
    cout << "xod: " << xod << endl;
    init();
    SOLVE();
  }
  
  puts("_____________________________________________________________________________________________________________");
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      cout << ANS[i][j];
    }cout << endl;
  }
  
  cout << endl << "Best: " << BEST << endl;
}
/*
найти компоненту с большим size'ом
bfs (строить дерево)
*/

nowruz2.out

nowruz3.out

nowruz4.out

nowruz5.out

nowruz6.out

nowruz7.out

nowruz8.out

nowruz9.out

nowruz10.out

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10