結果

問題 No.3602 Queen XOR Score
コンテスト
ユーザー askr58
提出日時 2026-07-24 23:02:42
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,875 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,329 ms
コンパイル使用メモリ 198,012 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2026-07-24 23:02:46
合計ジャッジ時間 3,527 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 27 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <ranges>
#include <bitset>
#include <algorithm>
#include <vector>
using namespace std;
using ll=long long;
int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int h,w;
	cin>>h>>w;
	vector<vector<ll>> a(h,vector<ll>(w));
	for(int i=0;i<h;i++)for(int j=0;j<w;j++)cin>>a[i][j];
	vector<bitset<400>> bs(60);
	vector<ll> basis(60);
	for(int i=0;i<h;i++)for(int j=0;j<w;j++){
		ll x=a[i][j];
		bitset<400> bit;
		bit[i*w+j]=1;
		for(int k=59;k>=0;k--){
			if(x>(x^basis[k])){
				bit^=bs[k];
				x^=basis[k];
			}
		}
		if(x>0){
			int msb=0;
			for(int i=0;i<60;i++)if(x>>i&1)msb=i;
			basis[msb]=x;
			bs[msb]=bit;
			for(int k=59;k>msb;k--){
				if(basis[k]>(basis[k]^x)){
					basis[k]^=x;
					bs[k]^=bit;
				}
			}
		}
	}
	int q;
	cin>>q;
	while(q--){
		ll x;
		cin>>x;
		if(x==0){
			cout<<4<<endl;
			cout<<1<<" "<<1<<endl;
			cout<<1<<" "<<2<<endl;
			cout<<1<<" "<<1<<endl;
			cout<<1<<" "<<2<<endl;
			continue;
		}
		bitset<400> bit;
		for(int i=59;i>=0;i--){
			if(x>(x^basis[i])){
				x^=basis[i];
				bit^=bs[i];
			}
		}
		if(x>0){
			cout<<-1<<endl;
			continue;
		}
		vector<array<int,2>> ans;
		int nx=-1,ny=-1;
		for(int i=0;i<h;i++){
			vector<int> v;
			for(int j=0;j<w;j++){
				if(bit[i*w+j])v.push_back(j);
			}
			if(v.empty())continue;
			if(nx==-1){
				for(int j=0;j<v.size();j++){
					ans.push_back({i+1,v[j]+1});
				}
				nx=i;ny=v.back();
			}else{
				bool f=false;
				for(int t:v)if(t==ny)f=true;
				if(f){
					ans.push_back({i+1,ny+1});
					int nny=ny;
					for(int t:v){
						if(t==ny)continue;
						ans.push_back({i+1,t+1});
						nny=t;
					}
					nx=i;
					ny=nny;
				}else{
					ans.push_back({i+1,ny+1});
					for(int t:v)ans.push_back({i+1,t+1});
					ans.push_back({i+1,ny+1});
					nx=i;
				}
			}
		}
		cout<<ans.size()-1<<endl;
		for(auto[x,y]:ans)cout<<x<<" "<<y<<endl;
	}
}
0