#1108113 (C++17(gcc12)) No.5022 XOR Printer

提出ソース

結果

問題	No.5022 XOR Printer
コンテスト
ユーザー	sig_256
提出日時	2025-07-26 16:57:53
言語	C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
結果	AC
実行時間	897 ms / 2,000 ms
コード長	6,501 bytes
コンパイル時間	2,897 ms
コンパイル使用メモリ	98,844 KB
実行使用メモリ	7,720 KB
スコア	4,799,911,557
最終ジャッジ日時	2025-07-26 17:01:11
合計ジャッジ時間	38,997 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
other	AC * 50

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <utility>
#include <array>
#include <vector>
#include <set>


#ifndef INT_HPP
#define INT_HPP

#include <cstdint>

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

#define U8MAX UINT8_MAX // 255
#define U16MAX UINT16_MAX // 65535
#define U32MAX UINT32_MAX // 4294967295 > 4.29*10⁹
#define U64MAX UINT64_MAX // 18446744073709551615 > 1.84*10¹⁹

using i8 = std::int8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;

#define I8MIN INT8_MIN // -128
#define I16MIN INT16_MIN // -32768
#define I32MIN INT32_MIN // -2147483648 < -2.14*10⁹
#define I64MIN INT64_MIN // -9223372036854775808 < -9.22*10¹⁸

#define I8MAX INT8_MAX // 127
#define I16MAX INT16_MAX // 32767
#define I32MAX INT32_MAX // 2147483647 > 2.14*10⁹
#define I64MAX INT64_MAX // 9223372036854775807 > 9.22*10¹⁸


#ifdef __SIZEOF_INT128__
using u128 = __uint128_t;
using i128 = __int128_t;
#define U128MAX u128(u128(0) - 1) // 340282366920938463463374607431768211455 > 3.40*10³⁸
#define I128MAX i128(U128MAX >> 1) // 170141183460469231731687303715884105727 > 1.70*10³⁸
#define I128MIN i128(-I128MAX - 1) // -170141183460469231731687303715884105728 < -1.70*10³⁸
#endif



#include <cstddef>
using std::size_t;
using std::byte;


#endif

#ifndef FLOAT_HPP
#define FLOAT_HPP

#include <cfloat>

using f32 = float;
using f64 = double;
using f128 = long double;

#endif



const u8 N = 10;
const u16 T = 1000;

class YX {
	public:
	u8 y = 0, x = 0;
	YX() {}
	YX(u8 _y, u8 _x) : y(_y), x(_x) {}
	u8 dist(const YX & other) const{
		u8 res = 0;
		if(y > other.y) res += y - other.y;
		else res += other.y - y;
		if(x > other.x) res += x - other.x;
		else res += other.x - x;
		return res;
	}
	bool operator<(const YX & other) const{
		if(x != other.x) return x < other.x;
		else return y < other.y;
	}
};

using Target = std::pair<YX, u32>;
struct Targetcomp{
	bool operator()(const Target & a, const Target & b) const{
		return a.first < b.first;
	}
};
using TargetsSet = std::set<Target, Targetcomp>;

class Num {
	u32 val;
	public:
	u32 get() const{
		return val;
	}
	void set(const u32 a){
		val = a;
	}
	void w(const u32 s){
		val ^= s;
	}

	u32 score(const u32 s) const{
		u32 nval = val ^ s;
		if(nval < val) return 0;
		else return nval - val;
	}
};

std::array<std::array<Num, N>, N> A_base, A;

namespace ANS {
	std::string ans;
	void moveto(YX from, YX to){
		while(from.x > to.x) ans.push_back('L'), from.x --;
		while(from.x < to.x) ans.push_back('R'), from.x ++;
		while(from.y > to.y) ans.push_back('U'), from.y --;
		while(from.y < to.y) ans.push_back('D'), from.y ++;
	}
	void write(){
		ans.push_back('W');
	}
	void get(){
		ans.push_back('C');
	}
}

namespace IO {
	void in(){
		u16 _N, _T;
		std::cin >> _N >> _T;
		for(u8 y = 0; y < N; ++y){
			for(u8 x = 0; x < N; ++x){
				u32 a;
				std::cin >> a;
				A_base[y][x].set(a);
				A[y][x].set(a);
			}
		}
	}
	void out(){
		u16 len = T;
		if(ANS::ans.size() < len) len = ANS::ans.size();
		for(u16 t = 0; t < len; ++t){
			std::cout << ANS::ans[t] << '\n';
		}
		std::cout << std::flush;
	}
}


inline TargetsSet::const_iterator execute_nearest(const TargetsSet & targets, const YX & from){
	TargetsSet::const_iterator res = targets.begin();
	f64 max_efficiency = 0, efficiency;
	for(auto it = targets.begin(); it != targets.end(); ++it){
		efficiency = it->second / (from.dist(it->first) + 1);
		if(efficiency > max_efficiency){
			max_efficiency = efficiency;
			res = it;
		}
	}
	return res;
}

f64 execute(bool simulate, YX & from, u32 s, u16 offset){
	TargetsSet targets;
	for(u8 y = 0; y < N; ++y){
			if(ANS::ans.size() < 900 &&(y == 4 || y == 5)) continue;
		for(u8 x = 0; x < N; ++x){
			targets.emplace(YX{y, x}, A[y][x].score(s));
		}
	}
	f64 max_efficiency = 0, efficiency;
	u32 total = 0;
	while(true){
		if(targets.empty()) break;
		auto nearest = execute_nearest(targets, from);
		u8 dist = from.dist(nearest->first);
		total += nearest->second;
		offset += dist + 1;
		efficiency = total / offset;
		if(max_efficiency > efficiency) break;
		max_efficiency = efficiency;
		if(!simulate){
			ANS::moveto(from, nearest->first);
			ANS::write();
			A[nearest->first.y][nearest->first.x].w(s);
		}
		from = nearest->first;
		targets.erase(nearest);
	}
	return max_efficiency;
}

u16 s_update(const std::vector<YX> & src, YX & from, u32 & s, u32 least){
	f64 max_efficiency = 0;
	u16 best_b = U16MAX;
	for(u16 b = 1; b < (1 << src.size()); ++b){
		u8 last = 0;
		u32 s_temp = s;
		for(u8 i = 0; i < src.size(); ++i){
			if(b & (1 << i)){
				s_temp ^= A[src[i].y][src[i].x].get();
				last = i;
			}
		}
		if(ANS::ans.size() == 296) std::clog << s_temp << ' ';
		if((least ^ s_temp) < least) continue;
		YX srcend = src[last];
		f64 efficiency = execute(true, srcend, s_temp, 1 + last);
		if(efficiency > max_efficiency){
			max_efficiency = efficiency;
			best_b = b;
		}
	}
	if(best_b == U16MAX) return 0;
	u8 offset = 0;
	for(u8 i = 0; i < src.size(); ++i){
		if(best_b & (1 << i)){
			offset += from.dist(src[i]) + 1;
			ANS::moveto(from, src[i]);
			from = src[i];
			s ^= A[src[i].y][src[i].x].get();
			ANS::get();
		}
	}
	std::clog << s << ' ';
	return offset;
}

std::vector<YX> route(YX from){
	std::vector<YX> res;
	if(from.y < 5){
		for(u8 i = 0; i < 5; ++i){
			if(from.y == 4) break;
			if(from.y > 1)
				res.emplace_back(from.y, from.x);
			from.y ++;
		}
	}
	else{
		for(u8 i = 0; i < 5; ++i){
			if(from.y == 5) break;
			if(from.y < 8)
				res.emplace_back(from.y, from.x);
			from.y --;
		}
	}
	u8 dx = (5 - res.size()) * 2 + 1;
	if(from.x < 5){
		while(--dx && from.x + 2 < N){
			from.x ++;
			res.emplace_back(from.y, from.x);
		}
		from.x ++;
	}
	else{
		while(--dx && from.x > 1){
			from.x --;
			res.emplace_back(from.y, from.x);
		}
		from.x --;
	}
	if(from.y == 4){
		while(res.size() < 10 && from.y > 0){
			from.y --;
			res.emplace_back(from.y, from.x);
		}
	}
	else{
		while(res.size() < 10 && from.y + 1 < N){
			from.y ++;
			res.emplace_back(from.y, from.x);
		}
	}
	return res;
}

u32 A_min(){
	u32 res = 1048576;
	for(u8 y = 0; y < N; ++y){
		for(u8 x = 0; x < N; ++x){
			if(A[y][x].get() < res){
				res = A[y][x].get();
			}
		}
	}
	return res;
}

int main(){
	IO::in();
	ANS::ans.reserve(T);
	u32 s = 0;
	YX me(0, 0);
	while(ANS::ans.size() < T){
		u16 offset = s_update(route(me), me, s, A_min());
		if(offset == 0) break;
		execute(false, me, s, offset);
	}
	IO::out();
	return 0;
}

yukicoder

結果

ソースコード