#include #include #include #include #include #include #include #include #include #include #include #include //#define LOCAL using namespace std; typedef vector VI; typedef vector< VI > VVI; typedef int64_t LL; typedef vector VD; //conversion //------------------------------------------ inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; } template inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); } //container util //------------------------------------------ #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(), (a).rend() #define PB push_back #define MP make_pair #define SZ(a) int((a).size()) #define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i) #define EXIST(s,e) ((s).find(e)!=(s).end()) #define SORT(c) sort((c).begin(),(c).end()) //repetition //------------------------------------------ #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) //#define LOG_ #if defined(__GNUC__) #include #define ASSERT_(x) assert(x) #else #include #define ASSERT_(x) assert(x) #endif //#define _DEBUG #ifdef _DEBUG #define dump(x) cerr << #x << '=' << (x) << endl; #define debug(x) cerr << #x << '=' << (x) << '('<<'L' << __LINE__ << ')' << ' ' << __FILE__ << endl; #define ASSERT(x) {if (!(x)){std::cout << "\nError!!\n" << "info string file:" << __FILE__ << " line:" << __LINE__ <<" "<< #x<< std::endl;ASSERT_(x);}} #endif #ifndef _DEBUG //#define ASSERT(X) { if (!(X)){std::cout << "\nError!!\n" << "info string file:" << __FILE__ << " line:" << __LINE__ <<" "<< #X<< std::endl; *(int*)1 =0;} } #define ASSERT(x) ((void)0) #define debug(x) ((void)0) #define dump(x) ((void)0) #endif #define CLR(a) memset((a), 0 ,sizeof(a)) unsigned long xor128() { static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123; unsigned long t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } unsigned long randomWrapper() { return xor128(); } #if defined(__GNUC__) #include #include #include LL starttime; inline LL now() { struct timeval tv; gettimeofday(&tv, NULL); LL t = tv.tv_sec * 1000LL + tv.tv_usec / 1000LL; return t; } inline LL elapsed() { return now() - starttime; } #else #include #include typedef std::chrono::milliseconds::rep TimePoint; inline TimePoint now() { return std::chrono::duration_cast(std::chrono::steady_clock::now().time_since_epoch()).count(); } TimePoint starttime; inline TimePoint elapsed() { return now() - starttime; } #endif LL Maxtime=980; std::mt19937 get_rand_mt; class matrix : public vector< vector > { private: int tate_, yoko_; public: matrix(const int tate__, const int yoko__) { assert(tate__ > 0); assert(yoko__ > 0); resize(tate__); for (size_t i = 0; i < size(); i++) { (*this)[i].resize(yoko__); } tate_ = tate__; yoko_ = yoko__; } matrix() {}; int tate()const { return tate_; } int yoko()const { return yoko_; } void resizematrix(const int tate__, const int yoko__) { assert(tate__ > 0); assert(yoko__ > 0); resize(tate__); for (size_t i = 0; i < size(); i++) { (*this)[i].resize(yoko__); } tate_ = tate__; yoko_ = yoko__; } void setone() { for (int i = 0; i Ls; // //const int maskfromy = 0b1111111; //const int maskfromx = maskfromy << 8; //const int masktoy = maskfromy << 16; //const int masktox = 0b1111111<<24; // //int32_t make_ans(int fromy, int fromx, int toy, int tox) { // int32_t a = fromy; // a |= (fromx << 8); // a |= (toy << 16); // a |= (tox << 24); // return a; //} // //string ret_ans(int32_t a) { // string s; // s += toString(a&maskfromy) + " " + toString(int(a&maskfromx)) + " " + toString(a&masktoy) + " " + toString(a&masktox); // return s; //} struct A { int fromx,fromy;int tox , toy; }; vector anss; //vector anss; inline std::ostream & operator<<(std::ostream & os, const A & a) { os << a.fromy+1 << " " << a.fromx+1 << " " << a.toy+1<<" " << a.tox+1; return os; } //#define LOG_ int initW = 0, W = 0, score = 0; //Xorなので2回動作させると元に戻る void domove(int fromy,int fromx,int toy,int tox) { if (fromx == tox) { for (int y = fromy; y <= toy; y++) { table[y][fromx] ^= 1; (table[y][fromx] == 1) ? score-- : score++; } } else if (fromy == toy) { for (int x = fromx; x <= tox; x++) { table[fromy][x] ^= 1; (table[fromy][x] == 1) ? score-- : score++; } } else { ASSERT(0); } } void domove(const A& a) { domove(a.fromy, a.fromx, a.toy, a.tox); } A makemoveRand(int length) { A a; int fromx = randomWrapper() % (N - length); int fromy = (randomWrapper() % N); //int fromy = 0; int tox = fromx + length - 1, toy = fromy; //int32_t a = make_ans(fromy, fromx, toy, tox); //cerr << a << endl; if (double(randomWrapper() % 6000) / 6000.0 < 0.5) { swap(fromx, fromy); swap(tox, toy); } a.fromx = fromx; a.fromy = fromy; a.toy = toy; a.tox = tox; return a; } int bestscore; vector SA() { vector bestAnss = anss; bestscore = score; besttable = table; LL t; double startTemp = 100; const double endTemp = 10; double cool = 0.99; double Temp = startTemp; while ((t=elapsed()) (double)(randomWrapper() % 10000) / 10000.0; bool better = newscore > bestscore; if (force||better) { anss[index] = b; if (better) { bestscore = newscore; bestAnss = anss; besttable = table; } } else { //元に戻す domove(b); domove(a); } //dump(Temp); //if (Temp < endTemp) { startTemp *= 0.99; Temp = startTemp; } } return bestAnss; } void solve() { anss.resize(K); //make ans REP(i, K) { int fromx = randomWrapper() % (N - Ls[i]); int fromy = (randomWrapper() % N); //int fromy = 0; int tox = fromx + Ls[i] - 1, toy = fromy; //int32_t a = make_ans(fromy, fromx, toy, tox); //cerr << a << endl; if (double(randomWrapper() % 6000) / 6000.0 < 0.5) { swap(fromx, fromy); swap(tox, toy); } anss[i].fromx = fromx; anss[i].fromy = fromy; anss[i].toy = toy; anss[i].tox = tox; } score = initW; //do_ans REP(i, K) { domove(anss[i].fromy, anss[i].fromx, anss[i].toy, anss[i].tox ); } anss=SA(); cerr << besttable << endl; } int main(int argc, char *argv[]) { starttime = now(); int seed = 0; if (argc >= 2) { seed = toInt(argv[1]); } #ifdef LOG_ string input = "./data/input" + toString(seed) + ".txt"; string output = "./data/output" + toString(seed) + ".txt"; #endif #ifdef LOCAL //MakeTestCase maketest; std::random_device rd; std::mt19937 mt(seed); table.resizematrix(N, N); Ls.resize(K); std::uniform_int_distribution Adice(0, 1); std::uniform_int_distribution Ldice(1, 25); REP(i, N)REP(j, N) { table[i][j] = Adice(mt); if (table[i][j] == 0) { initW++; } } REP(i, K) { Ls[i] = Ldice(mt); } #else cin >> N >> K; table.resizematrix(N, N); Ls.resize(K); REP(i, K) { cin >> Ls[i]; } REP(i, N){ string s; cin>>s; dump(s); REP(j, N) { table[i][j] = (s[j]-'0'); } } #endif #ifdef LOG_ ofstream ofs(input); ofs<