結果
| 問題 | 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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
| testcase_50 | WA | - |
| testcase_51 | WA | - |
| testcase_52 | WA | - |
ソースコード
// ランダムテストケース生成器
// パターンファイルは手動と自動で作りました
#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;
}