結果

問題 No.5002 stick xor
コンテスト
ユーザー polylogK
提出日時 2018-05-26 00:01:02
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 2,595 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,687 ms
実行使用メモリ 3,408 KB
スコア 0
最終ジャッジ日時 2018-05-26 00:01:13
ジャッジサーバーID
（参考情報） 		judge10 /
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using std::cout;
using std::endl;
using std::cin;

struct SegmentTree{
	std::vector<int> seg;
	int sz = 1;
	
	SegmentTree(int n){
		while(sz < n) sz *= 2;
		seg.assign(sz * 2, 0);
	}
	
	void update(int k, int x){
		k += sz - 1;
		seg[k] = x;
		
		while(k){
			k = (k - 1) / 2;
			seg[k] = seg[2 * k + 1];
		}
	}
	
	int get(int a, int b){
		return get(a, b, 0, 0, sz);
	}
	
	int get(int a, int b, int k, int l, int r){
		if(b<=l||r<=a) return 0;
		if(a<=l&&r<=b) return seg[k];
		
		return get(a, b, 2 * k + 1, l, (l + r) / 2) + get(a, b, 2 * k + 2, (l + r) / 2, r);
	}
	
	void reverse(int a, int b){
		for(int i = a; i < b; i++) update(i, 1 - get(i, i + 1));
	}
};

struct Node{
	int score;
	std::vector<SegmentTree> seg;
	std::vector<std::tuple<int, int, int, int>> vec;
	
	Node() {}
	Node(int score, std::vector<SegmentTree> seg, std::vector<std::tuple<int, int, int, int>> vec) : score(score), seg(seg), vec(vec) {};
	bool operator<(const Node b) const{return score > b.score;}
};

std::vector<int> l;
int n, k, K = 10, count = 0;

int main(){
	cin >> n >> k; std::vector<std::string> s(n); l.resize(k);
	for(int i = 0; i < k; i++) cin >> l[i];
	for(int i = 0; i < n; i++) cin >> s[i];
	
	std::vector<SegmentTree> seg(n, SegmentTree(n));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(s[i][j] == '0') {
				seg[i].update(j, 1);
				count++;
			}
		}
	}
	
	std::priority_queue<Node> qu[2];
	qu[0].push({0, seg, std::vector<std::tuple<int, int, int, int>>()});
	
	for(int i = 0; i < k; i++){
		while(!qu[i % 2].empty()){
			Node p = qu[i % 2].top(); qu[i % 2].pop();
			
			for(int x = 0; x < 20; x++){
				std::vector<SegmentTree> seg = p.seg;
				std::vector<std::tuple<int, int, int, int>> vec = p.vec;
				int A, B, C, D;
				
				if(rand() % 2) {
					A = rand() % n;
					B = A;
					C = rand() % (n - l[i] + 1);
					D = C + l[i] - 1;
				} else {
					C = rand() % n;
					D = C;
					A = rand() % (n - l[i] + 1);
					B = A + l[i] - 1;
				}
				
				for(int i = A; i < B; i++) seg[i].reverse(C, D);				
				int newscore = -count;
				for(int i = 0; i < n; i++) newscore += seg[i].get(0, n + 1);
				vec.push_back(std::tuple<int, int, int, int>(A + 1, C + 1, B + 1, D + 1));
				Node Np = Node{newscore, seg, vec};
				qu[1 - i % 2].push(Np);
				
				if(qu[1 - i % 2].size() > K) qu[1 - i % 2].pop();
			}
		}
	}
	
	Node p;
	while(!qu[k % 2].empty()) {
		p = qu[k % 2].top(); qu[k % 2].pop();
	}
	
	for(auto v : p.vec) cout << std::get<0>(v) << " " << std::get<1>(v) << " " << std::get<2>(v) << " " << std::get<3>(v) << endl;
	return 0;
}
0