QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#862536#9975. Hitoshizukuucup-team3695#WA 44ms9892kbC++205.3kb2025-01-19 02:47:382025-01-19 02:47:38

Judging History

你现在查看的是最新测评结果

  • [2025-01-19 02:47:38]
  • 评测
  • 测评结果:WA
  • 用时:44ms
  • 内存:9892kb
  • [2025-01-19 02:47:38]
  • 提交

answer

/* #region(collapsed) config_fwd */
#define O_NONE	  0
#define O_DEFAULT 1
#define O_O3	  2
#define O_OFAST	  3

#define T_NONE	  0
#define T_NO_TUNE 1
#define T_ALL	  2

#define OO_OFF 0
#define OO_ON  1
// OO_AUTO

#define TF_NONE 0
#define TF_META 1
// TF_AUTO

#define TC_NONE	 0
#define TC_COUNT 1
#define TC_UNTIL 2
/* #endregion */

// judge:
#define OO_AUTO OO_OFF
#define TF_AUTO TF_NONE
// debug on submission? (locally, CPLOCAL -> true, CPNDEBUG -> false)
#define DBG false
// optimize pragma (run/debug): none, default, O3, Ofast
#define ROPT O_O3
#define DOPT O_NONE
// targets: none, no tune, all
#define TGT T_ALL
// output-only mode (only locally): off, on, auto
#define OONLY OO_AUTO
// interactive?
#define INTER false
// test case format (TC_COUNT only): none, meta, auto
#define TC_FMT TF_AUTO
// test cases: none, count, until (go throws tc_stop)
#define TCASES TC_COUNT

/* #region(collapsed) */
/* #region(collapsed) config */
#ifdef CPLOCAL
#undef DBG
#define DBG true
#endif
#ifdef CPNDEBUG
#undef DBG
#define DBG false
#endif

#if DBG
#define OPT DOPT
#else
#define OPT ROPT
#endif

#if OPT == O_DEFAULT
#pragma GCC optimize("unroll-loops,no-stack-protector,fast-math")
#elif OPT == O_O3
#pragma GCC optimize("O3,unroll-loops,no-stack-protector,fast-math")
#elif OPT == O_OFAST
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#endif
/* #endregion */

/* #region(collapsed) STL */
#include <bits/extc++.h>
using namespace std;
namespace cr = std::chrono;
namespace rn = std::ranges;
namespace vw = std::views;
using namespace complex_literals;
using namespace chrono_literals;
using namespace string_literals;
using namespace string_view_literals;
/* #endregion */

/* #region(collapsed) abbrev */
#define TD(A, B)	  typedef B A;
#define iTDa(A, B, C) TD(A, B##C) TD(A##l, B##_least##C) TD(A##f, B##_fast##C)
#define iTD(S)		  iTDa(i##S, int, S##_t) iTDa(u##S, uint, S##_t)
iTD(8) iTD(16) iTD(32) iTD(64);
TD(imax, intmax_t) TD(umax, uintmax_t);
TD(iptr, intptr_t) TD(uptr, uintptr_t);
TD(i128, __int128_t) TD(u128, __uint128_t);

#undef TD
#undef iTDa
#undef iTD
/* #endregion */

/* #region(collapsed) chrono */
using h_clock	= cr::high_resolution_clock;
using s_clock	= cr::steady_clock;
using def_clock = h_clock;

template<class C = def_clock>
static inline auto now() noexcept
{
	return C::now();
}
template<class C = def_clock>
static inline auto epoch() noexcept
{
	return now<C>().time_since_epoch().count();
}
/* #endregion */

/* #region(collapsed) rng */
using rng_t		  = mt19937_64;
using rng_value_t = rng_t::result_type;

template<rng_value_t S = 314159265>
struct const_seeder
{
	static constexpr rng_value_t seed() noexcept
	{
		return S;
	}
};
template<class C = def_clock>
struct clock_seeder
{
	static inline rng_value_t seed() noexcept
	{
		return epoch<C>();
	}
};
struct device_seeder
{
	static inline rng_value_t seed() noexcept
	{
		random_device dev{};
		return uniform_int_distribution<rng_value_t>{numeric_limits<rng_value_t>::min(), numeric_limits<rng_value_t>::max()}(dev);
	}
};

using seeder = clock_seeder<>;

static rng_t randy(seeder::seed());
/* #endregion */

/* #region(collapsed) io */
// TODO
/* #endregion */

/* #region(collapsed) main */
static inline void pre();
static inline void go(size_t);

struct tc_stop
{};

static inline void tc_fmt(size_t i)
{
#if TCASES == TC_COUNT
#if TC_FMT == TF_META
	cout << "Case #" << i << ": ";
#endif
#endif
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	size_t tc;
#if TCASES == TC_NONE
	tc = 1;
#elif TCASES == TC_COUNT
	cin >> tc;
#elif TCASES == TC_UNTIL
	tc = numeric_limits<size_t>::max();
#endif

	for (size_t i = 0; i < tc; i++)
	{
#if TCASES == TC_COUNT && TC_FMT == TF_META
		cout << "Case #" << i << ": ";
#endif
		try
		{
			go(i);
		}
		catch (tc_stop)
		{
			break;
		}
	}
}
/* #endregion */
/* #endregion */

constexpr int N = 1e5;

struct girl
{
	int	 a, b;
	bool u;
};

alignas(64) static girl G[3 * N];
alignas(64) static int AI[3 * N], BI[3 * N], A[3 * N], Q[3 * N];

static inline void pre() {}

static inline void go(size_t)
{
	int n;
	cin >> n;
	for (int i = 0; i < 3 * n; i++)
	{
		cin >> G[i].a >> G[i].b;
		G[i].u = false;
		AI[i] = BI[i] = i;
	}

	auto constexpr proj_a = [](int i)
	{
		return G[i].a;
	};
	auto constexpr proj_b = [](int i)
	{
		return G[i].b;
	};
	rn::sort(AI, AI + 3 * n, {}, proj_a);
	rn::sort(BI, BI + 3 * n, {}, proj_b);
	int	 ai = 0, bi = 0, qi = 0;
	bool good = true;
	for (int i = 0; good & i < 3 * n; i += 3)
	{
		while (G[bi].u)
			bi++;
		int bj	= BI[bi];
		int b	= G[bj].b;
		A[i]	= bj;
		G[bj].u = true;
		while (ai < 3 * n && G[AI[ai]].a <= b)
		{
			int aj = AI[ai++];
			if (G[aj].u)
				continue;
			int a	= G[aj].a;
			Q[qi++] = aj;
			rn::push_heap(Q, Q + qi, greater{}, proj_b);
		}
		for (int j = 1; j <= 2;)
		{
			if (qi == 0)
			{
				good = false;
				break;
			}
			int aj = Q[0];
			rn::pop_heap(Q, Q + qi--, greater{}, proj_b);
			if (G[aj].u)
				continue;
			G[aj].u = true;
			A[i + j++] = aj;
		}
	}
	if (good)
	{
		cout << "Yes\n";
		for (int i = 0; i < 3 * n; i += 3)
			cout << A[i] + 1 << ' ' << A[i + 1] + 1 << ' ' << A[i + 2] + 1 << '\n';
	}
	else
		cout << "No\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9892kb

input:

2
2
1 2
2 2
2 3
3 5
4 4
4 5
1
1 1
1 1000000000
1000000000 1000000000

output:

Yes
1 2 3
5 4 6
No

result:

ok >_< (2 test cases)

Test #2:

score: 0
Accepted
time: 44ms
memory: 7920kb

input:

100000
1
164154503 167959139
178382610 336470888
12298535 642802746
1
165064830 773386884
353585658 396628655
792066242 971207868
1
1607946 2087506
21674839 46761498
9518201 16843338
1
262361007 691952768
190585553 787375312
637191526 693319712
1
41970708 45277106
197619816 762263554
308360206 40724...

output:

No
No
No
Yes
1 3 2
No
Yes
2 1 3
No
No
No
No
No
Yes
2 1 3
Yes
1 2 3
No
No
No
No
Yes
2 3 1
No
Yes
2 3 1
No
No
Yes
2 3 1
No
No
Yes
3 1 2
No
No
No
No
No
No
No
Yes
3 2 1
No
No
Yes
3 2 1
No
No
No
No
No
No
No
No
No
No
No
No
Yes
3 2 1
No
No
Yes
2 3 1
Yes
3 2 1
No
No
Yes
2 1 3
No
No
No
Yes
1 2 3
Yes
3 2 1
No...

result:

ok >_< (100000 test cases)

Test #3:

score: -100
Wrong Answer
time: 42ms
memory: 7764kb

input:

50000
2
36364670 641009859
15071436 75475634
20446080 476927808
357784519 503158867
206641725 322595515
268011721 645468307
2
247717926 939887597
808609669 973764525
496738491 710156469
463547010 860350786
757388873 784695957
29903136 208427221
2
26681139 67590963
458238185 475357775
80127817 135993...

output:

Yes
2 3 1
4 5 6
No
No
No
No
No
No
No
No
No
Yes
5 2 4
5 3 1
No
Yes
5 4 6
5 2 3
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
2 6 1
5 4 3
No
No
No
No
No
No
No
Yes
3 6 2
3 5 4
No
No
No
No
No
Yes
4 2 1
1 6 3
No
No
No
No
Yes
3 4 2
3 5 1
No
No
No
No
No
Yes
6 5 3
6 4 1
No
No
No
No
No
No
No
No
No
No
N...

result:

wrong answer There is no valid answer, but participant found one. (test case 1)