QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#862536 | #9975. Hitoshizuku | ucup-team3695# | WA | 44ms | 9892kb | C++20 | 5.3kb | 2025-01-19 02:47:38 | 2025-01-19 02:47:38 |
Judging History
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";
}
详细
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)