結果

問題 No.348 カゴメカゴメ
コンテスト
ユーザー moti
提出日時 2016-03-23 23:43:58
言語 Text
(cat 8.3)
結果
WA  
実行時間 -
コード長 7,114 bytes
コンパイル時間 146 ms
コンパイル使用メモリ 6,816 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-10-01 21:41:17
合計ジャッジ時間 1,795 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ランダムテストケース生成器
// パターンファイルは手動と自動で作りました
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>
#include <fstream>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)

template<class T> ostream& operator << (ostream& ost, vector<T> const& v) { rep(i, v.size()) { if(i) ost << endl; ost << v[i]; } ost << endl; return ost; }

template<class T> constexpr bool in_range(T y, T x, T H, T W) { return 0<=y&&y<H&&0<=x&&x<W; }
int dx[8] = {-1,0,1,0,-1,1,1,-1};
int dy[8] = {0,-1,0,1,-1,-1,1,1};

typedef long long ll;
int const inf = 1<<29;

struct xor128 {
  unsigned x,y,z,w;
  xor128(): x(std::random_device()()), y(std::random_device()()), z(std::random_device()()), w(std::random_device()()) {}
  unsigned next() {
    unsigned t=x^(x<<11);
    x=y;y=z;z=w;
    return w=w^(w>>19)^t^(t>>8);
  }
  unsigned next(unsigned k) {
    return next()%k;
  }
} rndgen;


vector<vector<string>> smalls =
{
#include "pattern_smalls"
};

vector<vector<string>> mediums =
{
#include "pattern_mediums"
};

vector<vector<string>> larges =
{
#include "pattern_larges"
};

vector<vector<string>> extreme_larges =
{
#include "pattern_extreme_larges"
};

vector<vector<string>> huges =
{
#include "pattern_huges"
};


void verify_patterns() {

  auto verify_field = [](vector<string> & v) {
    int N = v.size(), M = v[0].size();
    rep(y, N) rep(x, M) {

      if(v.size() != N) {
        cout << "v.size(): " << v.size() << " not equal to N = " << N << endl;
        exit(-1);
      }

      if(v[y].size() != M) {
        cout << "v["<<y<<"].size(): " << v[y].size() << " not equal to M = " << M << endl;
        exit(-1);
      }

      if(v[y][x] == '.') { continue; }

      if(v[y][x] != 'x') {
        cout << "unusable character\n";
        cout << "(x, y) = (" << x << ", " << y << ")\n";
        exit(-1);
      }

      int xcount = 0;
      rep(k, 8) {
        int ny = y + dy[k], nx = x + dx[k];
        if(!in_range(ny, nx, N, M)) { continue; }
        xcount += v[ny][nx] == 'x';
      }
      if(xcount != 2) {
        cout << "xcount = " << xcount << " not equal to 2.\n";
        cout << "(x, y) = (" << x << ", " << y << ")\n";
        exit(-1);
      }
    }
  };

  for(auto && v : smalls)         { cout << v << endl; verify_field(v); } puts("small pattern verified.");
  for(auto && v : mediums)        { cout << v << endl; verify_field(v); } puts("medium pattern verified.");
  for(auto && v : larges)         { cout << v << endl; verify_field(v); } puts("large pattern verified.");
  for(auto && v : extreme_larges) { cout << v << endl; verify_field(v); } puts("extreme large pattern verified.");
  for(auto && v : huges)          { cout << v << endl; verify_field(v); } puts("huge pattern verified.");

}

bool field[1000][1000];
bool work[1000][1000];

void copy_to_work_with_range(int y, int x, int PH, int PW) {
  REP(i, y, y + PH) REP(j, x, x + PW) {
    work[i][j] = field[i][j];
  }
}

void copy_to_field_with_range(int y, int x, int PH, int PW) {
  REP(i, y, y + PH) REP(j, x, x + PW) {
    field[i][j] = work[i][j];
  }
}

bool place_pattern_to_work(vector<string> const& pattern, int sy, int sx, int H, int W) {
  int PH = pattern.size(), PW = pattern[0].size();
  REP(i, sy, sy + PH) REP(j, sx, sx + PW) {
    if(pattern[i-sy][j-sx] == '.') { continue; }
    if(field[i][j]) { return false; }
    int xcount = 0;
    rep(k, 8) {
      int ni = i + dy[k], nj = j + dx[k];
      if(!in_range(ni, nj, H, W)) { continue; }
      if(in_range(ni, nj, sy+PH, sx+PW)) {
        xcount += work[ni][nj];
      } else {
        xcount += field[ni][nj];
      }
      if(work[ni][nj] && field[ni][nj]) { return false; }
    }
    if(xcount <= 2) {
      work[i][j] = 1;
    } else if(pattern[i-sy][j-sx] != '.') {
      return false;
    }
  }
  return true;
}

bool try_to_place_pattern(vector<string> const& pattern, int H, int W) {

  int PH = pattern.size(), PW = pattern[0].size();

  if(H < PH || W < PW) { return false; }

  int MaxTrials = 20;
  // Trial
  bool ok = 0;
  rep(trial, MaxTrials) {
    int y = H == PH ? 0 : rndgen.next(H - PH), x = W == PW ? 0 : rndgen.next(W - PW);
    copy_to_work_with_range(y, x, PH, PW);
    if(!place_pattern_to_work(pattern, y, x, H, W)) { continue; }
    ok = 1;
    copy_to_field_with_range(y, x, PH, PW);
    break;
  }
  return ok;
}

int N;
string fname_prefix;
int MaxPaintHuge;
int MaxPaintExL;
int MaxPaintLarge;
int MaxPaintMedium;
int MaxPaintSmall;

void make_random_pattern(int H, int W) {

  auto trial_result_message = [](bool ok, string const& msg){
    cout << msg << " trial ";
    if(ok) cout << "succeeded." << endl;
    else   cout << "failed." << endl;
  };

  bool ok = 1;
  rep(i, MaxPaintHuge) {
    int tryidx = rndgen.next(huges.size());
    ok &= try_to_place_pattern(huges[tryidx], H, W);
  }
  trial_result_message(ok, "Huge");

  ok = 1;
  rep(i, MaxPaintExL) {
    int tryidx = rndgen.next(extreme_larges.size());
    ok &= try_to_place_pattern(extreme_larges[tryidx], H, W);
  }
  trial_result_message(ok, "ExLarge");

  ok = 1;
  rep(i, MaxPaintLarge) {
    int tryidx = rndgen.next(larges.size());
    ok &= try_to_place_pattern(larges[tryidx], H, W);
  }
  trial_result_message(ok, "Large");
  
  ok = 1;
  rep(i, MaxPaintMedium) {
    int tryidx = rndgen.next(mediums.size());
    ok &= try_to_place_pattern(mediums[tryidx], H, W);
  }
  trial_result_message(ok, "Medium");
  
  ok = 1;
  rep(i, MaxPaintSmall) {
    int tryidx = rndgen.next(smalls.size());
    ok &= try_to_place_pattern(smalls[tryidx], H, W);
  }
  trial_result_message(ok, "Small");
  
}


int main() {

  verify_patterns();
  while(1) {
    cout << "\n----------------------------------------\n";  
    cout << endl;

    cout << "Which size do you want? [Height, Width]\n";
    int H, W; cin >> H >> W;
    if(cin.eof()) { break; }
    assert(1 <= H && H <= 1000 && 1 <= W && W <= 1000);

    cout << "What is file name prefix?\n";
    cin >> fname_prefix;
    cout << "How many files do you want?: [1,...]\n";
    cin >> N;

    cout << "Max Paint? [Huge, ExL, Large, Medium, Small]\n";  
    cin >> MaxPaintHuge
    >> MaxPaintExL
    >> MaxPaintLarge
    >> MaxPaintMedium
    >> MaxPaintSmall;

    cout << "Making random patten field...\n\n";

    rep(fturn, N) {
      cout << "\nPatten - " << fturn + 1 << "\n";
      make_random_pattern(H, W);
      ofstream ofs(("newpat/" + fname_prefix + to_string(fturn + 1)).c_str());
      ofs << H << " " << W << endl;
      rep(i, H) rep(j, W) {
        ofs << (field[i][j] ? 'x' : '.');
        if(j == W-1) ofs << endl;
      }
    }
  }
  return 0;
}
0