QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#861337 | #9975. Hitoshizuku | ucup-team6275# | WA | 0ms | 3712kb | C++20 | 23.0kb | 2025-01-18 17:00:48 | 2025-01-18 17:01:15 |
Judging History
answer
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <deque>
#include <set>
#include <random>
#include <cassert>
#include <chrono>
#include <bitset>
#include <queue>
using namespace std;
#include <iostream>
#include <cstring>
#include <immintrin.h>
#pragma GCC target("avx,avx2,popcnt")
#pragma GCC optimize("O3,unroll-loops")
class avx_bitset final {
private:
int n;
uint64_t* values;
int get_size() const {
return (n + 255) >> 8 << 2;
}
void expand(int new_n) {
int prev_size = get_size();
n = new_n;
int new_size = get_size();
if (new_size > prev_size) {
uint64_t* new_values = new uint64_t[new_size]{};
memcpy(new_values, values, sizeof(uint64_t) * prev_size);
delete[] values;
values = new_values;
}
}
void remove_trash() {
int sz = get_size();
if ((n >> 6) < sz) {
for (int i = (n >> 6) + 1; i < sz; i++)
values[i] = 0;
if (n & 63) {
values[n >> 6] <<= 64 - (n & 63);
values[n >> 6] >>= 64 - (n & 63);
} else {
values[n >> 6] = 0;
}
}
}
public:
avx_bitset(int n = 0, unsigned long long value = 0) : n(n) {
values = new uint64_t[get_size()]{};
for (int i = 0; i < n && i < 64; i++)
if (value >> i & 1)
set_bit(i, true);
}
avx_bitset(const avx_bitset &bs) : n(bs.n) {
int sz = get_size();
values = new uint64_t[sz];
memcpy(values, bs.values, sizeof(uint64_t) * sz);
}
int size() const {
return n;
}
void set_bit(int pos, bool bit) {
int id = pos >> 6;
pos &= 63;
if (bit)
values[id] |= uint64_t(1) << pos;
else
values[id] &= ~(uint64_t(1) << pos);
}
bool get_bit(int pos) const {
int id = pos >> 6;
pos &= 63;
return values[id] >> pos & 1;
}
avx_bitset& operator=(const avx_bitset &bs) {
delete[] values;
n = bs.n;
int sz = get_size();
values = new uint64_t[sz];
memcpy(values, bs.values, sizeof(uint64_t) * sz);
return *this;
}
avx_bitset& operator|=(const avx_bitset &bs) {
if (size() < bs.size())
expand(bs.size());
for (int i = 0; (i << 6) < bs.size(); i += 4)
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values + i),
_mm256_or_si256(_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + i)),
_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(bs.data() + i))));
return *this;
}
avx_bitset& operator&=(const avx_bitset &bs) {
if (size() < bs.size())
expand(bs.size());
for (int i = 0; (i << 6) < bs.size(); i += 4)
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values + i),
_mm256_and_si256(_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + i)),
_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(bs.data() + i))));
return *this;
}
avx_bitset& operator^=(const avx_bitset &bs) {
if (size() < bs.size())
expand(bs.size());
for (int i = 0; (i << 6) < bs.size(); i += 4)
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values + i),
_mm256_xor_si256(_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + i)),
_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(bs.data() + i))));
return *this;
}
avx_bitset& operator>>=(int shift) {
if (shift == 0 || n == 0)
return *this;
if (shift < 0)
return *this <<= -shift;
int sz = get_size();
if (!(shift & 255)) {
shift >>= 6;
if (shift > sz)
shift = sz;
int id = sz - shift;
for (int i = 0; i < id; i += 4)
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values + i),
_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + i + shift)));
memset(values + id, 0, sizeof(uint64_t) * shift);
} else if (!(shift & 63)) {
shift >>= 6;
if (shift > sz)
shift = sz;
int id = sz - shift, pos = 0;
for (; pos + 4 < id; pos += 4)
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values + pos),
_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + pos + shift)));
for (; pos < id; pos++)
values[pos] = values[pos + shift];
memset(values + id, 0, sizeof(uint64_t) * shift);
} else {
int d = shift >> 6, cnt1 = shift & 63, cnt2 = 64 - cnt1;
if (d >= sz) {
memset(values, 0, sizeof(uint64_t) * sz);
return *this;
}
int id = sz - 1 - d, pos = 0;
__m256i to_shift_right = _mm256_set1_epi64x(cnt1), to_shift_left = _mm256_set1_epi64x(cnt2);
for (; pos + 4 < id; pos += 4)
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values + pos),
_mm256_or_si256(_mm256_srlv_epi64(
_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + pos + d)),
to_shift_right),
_mm256_sllv_epi64(_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + pos + d + 1)),
to_shift_left)));
for (; pos < id; pos++)
values[pos] = (values[pos + d] >> cnt1) | (values[pos + d + 1] << cnt2);
values[id] = values[sz - 1] >> cnt1;
memset(values + id + 1, 0, sizeof(uint64_t) * d);
}
return *this;
}
avx_bitset& operator<<=(int shift) {
if (shift == 0 || n == 0)
return *this;
if (shift < 0)
return *this >>= -shift;
int sz = get_size();
if (!(shift & 255)) {
shift >>= 6;
if (shift > sz)
shift = sz;
for (int i = sz - 4; i >= shift; i -= 4)
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values + i),
_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + i - shift)));
memset(values, 0, sizeof(uint64_t) * shift);
} else if (!(shift & 63)) {
shift >>= 6;
if (shift > sz)
shift = sz;
int pos = sz - 1;
for (; pos >= shift + 3; pos -= 4)
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values + pos - 3),
_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + pos - 3 - shift)));
for (; pos >= shift; pos--)
values[pos] = values[pos - shift];
memset(values, 0, sizeof(uint64_t) * shift);
} else {
int d = shift >> 6, cnt1 = shift & 63, cnt2 = 64 - cnt1;
if (d >= sz) {
memset(values, 0, sizeof(uint64_t) * sz);
return *this;
}
int pos = sz - 1;
__m256i to_shift_left = _mm256_set1_epi64x(cnt1), to_shift_right = _mm256_set1_epi64x(cnt2);
for (; pos > d + 3; pos -= 4)
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values + pos - 3),
_mm256_or_si256(_mm256_sllv_epi64(
_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + pos - 3 - d)),
to_shift_left),
_mm256_srlv_epi64(_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + pos - 4 - d)),
to_shift_right)));
for (; pos > d; pos--)
values[pos] = (values[pos - d] << cnt1) | (values[pos - d - 1] >> cnt2);
values[d] = values[0] << cnt1;
memset(values, 0, sizeof(uint64_t) * d);
}
remove_trash();
return *this;
}
friend avx_bitset operator|(const avx_bitset &a, const avx_bitset &b) {
return avx_bitset(a) |= b;
}
friend avx_bitset operator&(const avx_bitset &a, const avx_bitset &b) {
return avx_bitset(a) &= b;
}
friend avx_bitset operator^(const avx_bitset &a, const avx_bitset &b) {
return avx_bitset(a) ^= b;
}
friend avx_bitset operator>>(const avx_bitset &a, int shift) {
return avx_bitset(a) >>= shift;
}
friend avx_bitset operator<<(const avx_bitset &a, int shift) {
return avx_bitset(a) <<= shift;
}
bool operator==(const avx_bitset &bs) const {
if (n != bs.size())
return false;
int sz = get_size();
for (int pos = 0; pos < sz; pos += 4)
if (!_mm256_testz_si256(_mm256_set1_epi32(-1),
_mm256_xor_si256(_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + pos)),
_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(bs.data() + pos)))))
return false;
return true;
}
bool operator!=(const avx_bitset &bs) const {
return !(*this == bs);
}
int find_next_one(int pos) const {
if (pos >= n)
return n;
int sz = get_size(), id = pos >> 6;
for (uint64_t value; (id & 3) || id == (pos >> 6); id++)
if (value = id == (pos >> 6) ? (values[id] >> (pos & 63) << (pos & 63)) : values[id])
return (id << 6) + __builtin_ctzll(value);
for (; id < sz; id += 4)
if (!_mm256_testz_si256(_mm256_set1_epi32(-1),
_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + id))))
break;
if (id == sz)
return n;
for (;; id++)
if (values[id])
return (id << 6) + __builtin_ctzll(values[id]);
}
int find_next_zero(int pos) const {
if (pos >= n)
return n;
int sz = get_size(), id = pos >> 6;
for (uint64_t value; (id & 3) || id == (pos >> 6); id++)
if (value = ~(id == (pos >> 6)
? (values[id] >> (pos & 63) << (pos & 63) | (uint64_t(1) << (pos & 63)) - 1) : values[id]))
return (id << 6) + __builtin_ctzll(value);
for (; id < sz; id += 4)
if (!_mm256_testz_si256(_mm256_set1_epi32(-1),
_mm256_xor_si256(_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + id)),
_mm256_set1_epi32(-1))))
break;
if (id == sz)
return n;
for (;; id++)
if (~values[id])
return (id << 6) + __builtin_ctzll(~values[id]);
}
int find_prev_one(int pos) const {
if (pos < 0)
return -1;
int id = pos >> 6;
for (uint64_t value; id >= 0 && ((id & 3) != 3 || id == (pos >> 6)); id--)
if (value = id == (pos >> 6) ? (values[id] << (63 - (pos & 63)) >> (63 - (pos & 63))) : values[id])
return (id << 6) + 63 - __builtin_clzll(value);
for (; id >= 0; id -= 4)
if (!_mm256_testz_si256(_mm256_set1_epi32(-1),
_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + id - 3))))
break;
if (id == -1)
return -1;
for (;; id--)
if (values[id])
return (id << 6) + 63 - __builtin_clzll(values[id]);
}
int find_prev_zero(int pos) const {
if (pos < 0)
return -1;
int id = pos >> 6;
for (uint64_t value; id >= 0 && ((id & 3) != 3 || id == (pos >> 6)); id--)
if (value = ~(id == (pos >> 6)
? ((values[id] << (63 - (pos & 63)) >> (63 - (pos & 63))) |
((pos & 63) == 63 ? 0 : (uint64_t(-1) - (uint64_t(1) << ((pos & 63) + 1)) + 1)))
: values[id]))
return (id << 6) + 63 - __builtin_clzll(value);
for (; id >= 0; id -= 4)
if (!_mm256_testz_si256(_mm256_set1_epi32(-1),
_mm256_xor_si256(_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + id - 3)),
_mm256_set1_epi32(-1))))
break;
if (id == -1)
return -1;
for (;; id--)
if (~values[id])
return (id << 6) + 63 - __builtin_clzll(~values[id]);
}
bool any() const {
int sz = get_size();
for (int id = 0; id < sz; id += 4)
if (!_mm256_testz_si256(_mm256_set1_epi32(-1),
_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + id))))
return true;
return false;
}
void flip() {
int sz = get_size();
for (int id = 0; id < sz; id += 4)
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values + id),
_mm256_xor_si256(_mm256_lddqu_si256(reinterpret_cast<const __m256i*>(values + id)),
_mm256_set1_epi32(-1)));
remove_trash();
}
int popcount() const {
int sz = get_size(), tot = 0;
for (int i = 0; i < sz; i++)
tot += __builtin_popcountll(values[i]);
return tot;
}
void set() {
memset(values, -1, sizeof(uint64_t) * get_size());
remove_trash();
}
void reset() {
memset(values, 0, sizeof(uint64_t) * get_size());
}
void set_segment(int l, int r) {
while (l < r && (l & 255))
set_bit(l++, true);
while (r > l && (r & 255))
set_bit(--r, true);
l >>= 6;
r >>= 6;
for (int id = l; id < r; id += 4)
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values + id),
_mm256_set1_epi64x(-1));
}
void reset_segment(int l, int r) {
while (l < r && (l & 255))
set_bit(l++, false);
while (r > l && (r & 255))
set_bit(--r, false);
l >>= 6;
r >>= 6;
for (int id = l; id < r; id += 4)
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values + id),
_mm256_setzero_si256());
}
explicit operator std::string() const {
std::string res(n, '0');
for (int i = 0; i < n; i++)
res[i] = '0' + get_bit(i);
return res;
}
explicit operator unsigned long long() const {
unsigned long long res = 0;
for (int i = n - 1; i >= 0; i--)
res = (res << 1) ^ get_bit(i);
return res;
}
friend std::ostream& operator<<(std::ostream &out, const avx_bitset &bs) {
out << std::string(bs);
return out;
}
uint64_t* data() const {
return values;
}
~avx_bitset() {
delete[] values;
}
};
const int MAX_PENALTY = 13 * (299 + 20 * 99);
const int MAX_SUB = 100;
const int MAX_MINUTE = 299;
const int MAX_TASK = 13;
avx_bitset dp[MAX_TASK + 1][MAX_TASK + 1];
struct Part {
int type;
//type = 0 => y x try, type = 1 => x try
int y, x;
};
void print_part(Part a) {
cout << " ";
if (a.type == 0) {
cout << a.y << " " << a.x;
if (a.x == 1) cout << " try";
else cout << "tries";
}
}
void solve() {
int n, m;
cin >> n >> m;
for (int it = 0; it < n; ++it) {
string s;
cin >> s;
bool found = false;
for (int pref_solved = 1; pref_solved <= 2; ++pref_solved) {
int val = 0;
for (int i = 0; i < pref_solved; ++i) {
val = val * 10 + s[i] - '0';
}
if (val > m) continue;
if (s[pref_solved] == '0' || !isdigit(s[pref_solved])) continue;
int penalty = 0;
for (int pref_penalty = pref_solved;;++pref_penalty) {
if (!isdigit(s[pref_penalty])) continue;
penalty = penalty * 10 + s[pref_penalty] - '0';
if (penalty > MAX_PENALTY) break;
vector <array <int, 3>> els;
int cur = pref_penalty + 1;
while (cur < s.size()) {
int l = cur;
while (s[cur] != 't') {
++cur;
}
int r = cur - 1;
if (s[cur + 2] == 'y') els.push_back({l, r, 0});
else els.push_back({l, r, 1});
while (cur < s.size() && !isdigit(s[cur])) cur++;
}
int ln = els.size();
for (int i = 0; i <= ln; ++i) {
for (int cnt_ok = 0; cnt_ok <= m; ++cnt_ok) {
dp[i][cnt_ok] = avx_bitset(penalty + 1);
}
}
dp[0][0].set_bit(0, true);
for (int i = 0; i < ln; ++i) {
int len = els[i][1] - els[i][0] + 1;
// y x try
for (int prev_ok = 0; prev_ok < min(m, i); ++prev_ok) {
int cur_minute = 0;
for (int len_minute = 1; len_minute < len; ++len_minute) {
cur_minute = cur_minute * 10 + s[els[i][0] + len_minute - 1] - '0';
if (cur_minute > MAX_MINUTE) break;
int cnt_submissions = 0;
if (s[els[i][0] + len_minute] == '0') continue;
for (int j = els[i][0] + len_minute; j <= els[i][1]; ++j) {
cnt_submissions = cnt_submissions * 10 + s[j] - '0';
}
if (cnt_submissions == 1 && els[i][2] == 1) continue;
if (cnt_submissions > 1 && els[i][2] == 0) continue;
if (cnt_submissions > MAX_SUB) continue;
int my_penalty = cur_minute + 20 * (cnt_submissions - 1);
dp[i + 1][prev_ok + 1] |= (dp[i][prev_ok] << my_penalty);
}
}
//x try
for (int prev_ok = 0; prev_ok < min(m, i); ++prev_ok) {
int cnt_submission = 0;
for (int j = els[i][0]; j <= els[i][1]; ++j) {
cnt_submission = cnt_submission * 10 + els[i][0] - '0';
}
if (cnt_submission > MAX_SUB) break;
dp[i + 1][prev_ok] |= dp[i][prev_ok];
}
}
if (dp[ln][val].get_bit(penalty)) {
int cur_penalty = penalty;
int cur_oks = val;
vector <Part> res;
for (int i = ln - 1; i >= 0; --i) {
int len = els[i][1] - els[i][0] + 1;
// y x try
bool okk = false;
if (cur_oks > 0) {
int cur_minute = 0;
for (int len_minute = 1; len_minute < len; ++len_minute) {
cur_minute = cur_minute * 10 + s[els[i][0] + len_minute - 1] - '0';
if (cur_minute > MAX_MINUTE) break;
int cnt_submissions = 0;
if (s[els[i][0] + len_minute] == '0') continue;
for (int j = els[i][0] + len_minute; j <= els[i][1]; ++j) {
cnt_submissions = cnt_submissions * 10 + s[j] - '0';
}
if (cnt_submissions == 1 && els[i][2] == 1) continue;
if (cnt_submissions > 1 && els[i][2] == 0) continue;
if (cnt_submissions > MAX_SUB) continue;
int my_penalty = cur_minute + 20 * (cnt_submissions - 1);
if (cur_penalty - my_penalty >= 0 && dp[i][cur_oks - 1].get_bit(cur_penalty - my_penalty)) {
okk = true;
cur_penalty -= my_penalty;
cur_oks--;
res.push_back({0, cur_minute, cnt_submissions});
break;
}
}
}
//x try
if (!okk) {
int cnt_submission = 0;
for (int j = els[i][0]; j <= els[i][1]; ++j) {
cnt_submission = cnt_submission * 10 + els[i][0] - '0';
}
if (cnt_submission > MAX_SUB) break;
if (dp[i][cur_oks].get_bit(cur_penalty)) {
okk = true;
res.push_back({1, 0, cnt_submission});
break;
}
}
assert(okk);
}
found = true;
reverse(res.begin(), res.end());
cout << val << " " << penalty;
for (auto i : res) {
print_part(i);
}
cout << "\n";
break;
}
}
if (found) break;
}
}
}
signed main() {
if (1) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
}
int t = 1;
while (t--) {
solve();
}
return 0;
}
/*
5 7
1 2
1 3
2 4
2 5
A 1 4 2
A 3 5 2
D 1 4
D 2 3
D 2 1
A 5 5 10
D 5 100
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3712kb
input:
2 2 1 2 2 2 2 3 3 5 4 4 4 5 1 1 1 1 1000000000 1000000000 1000000000
output:
result:
wrong output format Unexpected end of file - token expected (test case 1)