結果

問題 No.5024 魔法少女うなと宝集め
コンテスト
ユーザー Kinoko_Sokora
提出日時 2026-05-02 17:48:21
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 5,331 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,094 ms
コンパイル使用メモリ 180,532 KB
実行使用メモリ 6,400 KB
スコア 1,657,996
最終ジャッジ日時 2026-05-02 17:49:29
合計ジャッジ時間 6,093 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<stack>
#include<iomanip>
#include<queue>
#include<set>
#include<functional>
#include<tuple>
#include<bitset>
#include<cassert>
#include<cstdint>
#include<complex>
#include<random>
#include<fstream>
#include <unordered_map>  
#include <unordered_set>  
using namespace std;
bool printb(bool f) {
	if (f)printf("Yes\n");
	else printf("No\n");
	return f;
}
template<class T>
void prt(T t = "", string sep = "\n") { cout << t << sep; return; }
template<class T>
void printl(vector<T> a, string sep = " ") {
	for (int i = 0; i < a.size(); i++) {
		cout << a[i];
		if (i != a.size() - 1)cout << sep;
	}
	cout << "\n";
	return;
}

bool prt_isfixed = false;
template<class T>
void prt_fix(T t, string sep = "\n") {
	if (!prt_isfixed) {
		cout << fixed << setprecision(15);
		prt_isfixed = true;
	}
	prt(t, sep);
}
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
/*
#pragma GCC target "prefer-vector-width=512"
#pragma GCC optimize "Ofast"
#pragma GCC optimize("unroll-loops")
*/
using uint = unsigned int;
using llong = long long;
using ullong = unsigned long long;
using pii = pair<int, int>;
using pll = pair<llong, llong>;
using pli = pair<llong, int>;
using pil = pair<int, llong>;
template<typename T> using vec2 = vector<vector<T>>;
template<typename T> inline bool chmin(T& a, T b) { return (a > b) ? (a = b, true) : false; }
template<typename T> inline bool chmax(T& a, T b) { return (a < b) ? (a = b, true) : false; }
bool bitIn(llong a, int b) { return ((a >> b) & 1); }
int bitCnt(llong a) {
	int re = 0;
	while (a > 0) {
		if (a & 1)re++;
		a >>= 1;
	}
	return re;
}
llong powL(llong n, llong i) {
	llong re = 1;
	while (i >= 1) {
		if (i & 1) re *= n;
		n *= n;
		i >>= 1;
	}
	return re;
}
llong powL_M(llong n, llong i, llong mod) {
	llong re = 1;
	while (i >= 1) {
		if (i & 1) {
			re *= n;
			re %= mod;
		}
		n *= n;
		n %= mod;
		i >>= 1;
	}
	return re;
}


llong cei(llong a, llong b) {
	if (a % b == 0)return a / b;
	else if (a < 0) {
		return a / b;
	}
	else {
		return a / b + 1;
	}
}

llong flo(llong a, llong b) {
	if (a % b == 0)return a / b;
	else if (a < 0) {
		return a / b - 1;
	}
	else {
		return a / b;
	}
}
int  dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int  dx2[8] = { -1,-1,1,1,-1,-1,1,1 }, dy2[8] = { 1,-1,-1,1,1,-1,-1,1 };
int dx8[8] = { 0,1,1,1,0,-1,-1,-1 }, dy8[8] = { -1,-1,0,1,1,1,0,-1 };

int rand_range(int min_val, int max_val) {
	// 乱数生成器
	static std::mt19937_64 mt64(123);
	
	// [min_val, max_val] の一様分布整数 (int) の分布生成器
	std::uniform_int_distribution<int> get_rand_uni_int(min_val, max_val);
	
	// 乱数を生成
	return get_rand_uni_int(mt64);
}

int n,t;
vec2<int> a;

void output(vector<pii>& a){
	prt(a.size());
	rep(i,a.size()){
		printf("%d %d\n",a[i].first,a[i].second);
	}
}


bool minum(vector<pii>& re,int sx,int sy){
		vec2<bool> bo(n,vector<bool>(n,false));
		bool isFail = false;
		int nx=sx,ny=sy;
		re.emplace_back(nx,ny);
		while(re.size()<t){
			bo[nx][ny]=true;
			int to2 = 0,ind = -1;
			rep(k,4){
				if(clamp(nx+dx[k],0,n-1)!=nx+dx[k])continue;
				if(clamp(ny+dy[k],0,n-1)!=ny+dy[k])continue;
				if(bo[nx+dx[k]][ny+dy[k]])continue;
				if(chmax(to2,a[nx+dx[k]][ny+dy[k]]))ind=k;
			}
			if(ind==-1){
				isFail=true;
				break;
			}
			nx+=dx[ind];
			ny+=dy[ind];
			re.emplace_back(nx,ny);
		}
		reverse(all(re));
		nx = sx;
		ny=sy;
		isFail = false;
		while(re.size()<t){
			bo[nx][ny]=true;
			int to2 = 0,ind = -1;
			rep(k,4){
				if(clamp(nx+dx[k],0,n-1)!=nx+dx[k])continue;
				if(clamp(ny+dy[k],0,n-1)!=ny+dy[k])continue;
				if(bo[nx+dx[k]][ny+dy[k]])continue;
				if(chmax(to2,a[nx+dx[k]][ny+dy[k]]))ind=k;
			}
			if(ind==-1){
				isFail=true;
				break;
			}
			nx+=dx[ind];
			ny+=dy[ind];
			re.emplace_back(nx,ny);
		}
		if(isFail){
			re.clear();
			return false;
		}
		return true;

}

int sc_cnt(vector<pii>& re2){
	int re=0;
	for(auto [i,j]:re2){
		re+=a[i][j];
	}
	return re;
}
void sample(vector<pii>& path){
	int N=n,T=t;
  for (int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            // 左から右へ
            for (int j = 0; j < N; j++) {
                path.push_back(make_pair(i, j));
                if (path.size() == T) {
                    break;
                }
            }
        } else {
            // 右から左へ
            for (int j = N - 1; j >= 0; j--) {
                path.push_back(make_pair(i, j));
                if (path.size() == T) {
                    break;
                }
            }
        }

        if (path.size() == T) {
            break;
        }
    }
	return;
}

int main() {
	cin>>n>>t;
	a.resize(n,vector<int>(n));
	rep(i,n)rep(j,n)scanf("%d",&a[i][j]);

	if(t<100||true){
		vector<tuple<int,int,int>> rank;
		rep(i,n){
			rep(j,n){
				rank.emplace_back(a[i][j],i,j);
			}
		}
		//prt("d");
		sort(all(rank));
		reverse(all(rank));
		int in=0;
		vector<pii> re2;
		sample(re2);
		//prt("ds");
		int sc_nw=sc_cnt(re2);
		while(clock()/CLOCKS_PER_SEC<1.95&&in<n*n){
			vector<pii> re;
			minum(re,get<1>(rank[in]),get<2>(rank[in]));
			int sc=sc_cnt(re);
			if(chmax(sc_nw,sc)){
				swap(re,re2);
			}
			in++;
		}
		
		

		output(re2);

	}else{

	}

    return 0;

}
0