QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#726636 | #3619. Restroom Monitor | nickbelov# | AC ✓ | 29ms | 8344kb | C++20 | 2.8kb | 2024-11-09 04:34:02 | 2024-11-09 04:34:02 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;
struct chash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
constexpr ll NN = 2e5, M = 1000000007, L = 20;
ll f1[NN], f2[NN];
ll inv(ll a, ll b=M) { return 1 < a ? b - inv(b % a, a) * b / a : 1; } // inv a mod b
ll choose(ll n, ll k) { return f1[n] * f2[k] % M * f2[n - k] % M; } // n choose k
void run()
{
int s, n;
cin>>s>>n;
vi yes, no;
for (int i = 0; i < n; i++) {
int d;
char t;
cin>>d>>t;
if (t == 'y') {
yes.push_back(d);
} else {
no.push_back(d);
}
}
sort(A(yes));
sort(A(no));
reverse(A(yes));
set<int> taken;
for (auto x : yes) {
int t = x;
if (taken.size()) t = min(t, *taken.begin() - 1);
taken.insert(t);
}
if (taken.size() && *taken.begin() <= 0) {
cout << "No";
return;
}
int idx = 0;
int t = 0;
while (idx < (int)no.size()) {
t++;
if (t > no[idx]) {
cout << "No";
return;
}
if (taken.count(t)) idx += s - 1;
else idx += s;
}
cout << "Yes";
}
int main()
{
//KING OF THE WORLD...... U.W.T.B
cin.tie(0);
ios_base::sync_with_stdio(false);
run();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3620kb
input:
3 7 2 y 2 n 5 y 1 n 5 n 2 y 1 n
output:
Yes
result:
ok single line: 'Yes'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
2 7 2 y 2 n 5 y 1 n 5 n 2 y 1 n
output:
No
result:
ok single line: 'No'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
1 10 1 y 2 y 3 y 4 y 5 y 6 y 7 y 8 y 9 y 10 y
output:
Yes
result:
ok single line: 'Yes'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
1 10 1 y 1 y 3 y 4 y 5 y 6 y 7 y 8 y 9 y 10 y
output:
No
result:
ok single line: 'No'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
1 10 10 y 10 y 10 y 10 y 10 y 10 y 10 y 10 y 10 y 10 y
output:
Yes
result:
ok single line: 'Yes'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
1 11 10 y 10 y 10 y 10 y 10 y 10 y 10 y 10 y 10 y 10 y 1 n
output:
No
result:
ok single line: 'No'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
1 10 10 y 10 y 10 y 10 y 10 y 5 y 5 y 5 y 5 y 5 y
output:
Yes
result:
ok single line: 'Yes'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
1 10 10 y 10 y 10 y 10 y 10 y 5 y 5 y 2 y 2 y 1 y
output:
No
result:
ok single line: 'No'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3804kb
input:
50000 100000 1 y 10 y 100 y 1000 y 10000 y 100000 y 1000000 y 10000000 y 100000000 y 1000000000 y 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 ...
output:
Yes
result:
ok single line: 'Yes'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3732kb
input:
50000 100000 1 y 10 y 100 y 1000 y 10000 y 100000 y 1000000 y 10000000 y 100000000 y 1000000000 y 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 n 1 ...
output:
No
result:
ok single line: 'No'
Test #11:
score: 0
Accepted
time: 29ms
memory: 8344kb
input:
50000 100000 935452939 y 346906478 y 226380928 y 664005726 y 752392575 y 344555276 y 911408648 y 444148178 y 177098804 y 841719276 y 628907979 y 687014518 y 315560756 y 248858564 y 394782185 y 576348946 y 353692902 y 824189669 y 620606082 y 954905813 y 904341853 y 829052518 y 218785860 y 721564387 y...
output:
Yes
result:
ok single line: 'Yes'
Test #12:
score: 0
Accepted
time: 16ms
memory: 5764kb
input:
677 91815 63153 y 84760 n 66486 n 75944 y 55200 n 82567 n 46368 n 91253 n 84920 y 53370 y 5319 n 33998 n 1960 n 43252 y 44533 n 31120 y 77178 y 26692 n 17322 y 45898 y 91336 y 80330 n 76309 y 54614 y 70461 y 74900 y 95113 y 79961 y 7964 y 14832 y 91584 n 2487 n 15988 y 59823 n 9061 n 62222 y 6580 n ...
output:
Yes
result:
ok single line: 'Yes'
Test #13:
score: 0
Accepted
time: 9ms
memory: 5176kb
input:
831 69194 74600 n 37699 n 38735 n 66971 n 52940 n 2652 y 97497 n 65707 y 61251 n 27792 n 1182 n 75259 n 1610 n 13174 y 64688 n 40975 n 49938 n 96246 n 69928 n 70360 y 5614 y 9869 y 22308 n 73842 n 6079 n 38315 y 65354 y 60128 n 67005 y 26435 y 89049 n 99514 n 86276 y 54943 y 46994 y 20096 y 70684 n ...
output:
Yes
result:
ok single line: 'Yes'
Test #14:
score: 0
Accepted
time: 18ms
memory: 6144kb
input:
965 97890 9073 n 88160 n 927 y 87345 n 60300 n 49784 n 65573 y 61485 n 72387 y 96238 n 67568 n 48201 n 91243 n 78299 y 68480 n 66590 y 39732 y 54179 n 67663 n 80547 n 45918 n 46005 y 64554 y 84741 n 48823 y 97045 n 86101 y 13210 n 89032 y 90458 n 43046 y 14819 y 13076 n 78797 y 13736 n 45285 y 55584...
output:
No
result:
ok single line: 'No'
Test #15:
score: 0
Accepted
time: 13ms
memory: 5332kb
input:
302 75573 63973 y 11621 y 10990 y 12252 n 71474 n 99116 n 23022 n 19306 n 67064 y 69830 n 5545 y 46729 y 64088 y 95856 n 81304 n 69948 n 12715 n 50286 n 91165 n 95558 y 4893 y 86508 n 17043 y 77419 n 93710 n 95291 n 74755 y 47095 n 872 n 26298 y 82877 n 19818 n 64855 n 20427 y 13242 y 67243 y 27518 ...
output:
Yes
result:
ok single line: 'Yes'
Test #16:
score: 0
Accepted
time: 17ms
memory: 5940kb
input:
79 99198 9274 y 3939 y 69 y 3073 y 943 y 2709 y 2818 n 1550 y 166 y 6626 y 2673 y 2820 y 537 n 4163 n 7863 n 5696 n 7415 y 735 y 3785 n 8020 y 8163 y 6265 n 9540 n 4931 y 4399 n 1192 y 1846 y 8218 n 2892 n 5137 y 4944 n 7393 y 1772 y 8931 n 4004 y 8407 n 9618 n 1170 y 9237 y 7609 n 7797 n 6330 y 422...
output:
No
result:
ok single line: 'No'
Test #17:
score: 0
Accepted
time: 14ms
memory: 5756kb
input:
29 82698 8640 n 174 y 2524 y 6813 n 7819 n 811 y 2442 y 3998 y 9966 y 1856 y 1100 y 5464 n 6697 n 8104 n 4611 y 2364 y 2562 n 9236 n 7380 n 2968 n 39 n 8694 y 355 y 2825 y 4525 n 1956 y 9788 y 8647 n 3208 n 2642 y 1522 n 3249 y 6320 y 5912 y 1476 y 756 n 6859 n 734 y 4770 n 9084 n 5640 n 3530 y 4924...
output:
No
result:
ok single line: 'No'
Test #18:
score: 0
Accepted
time: 12ms
memory: 5612kb
input:
83 85808 16724 y 36413 y 32160 n 20799 n 23512 y 23271 n 24923 y 47881 y 335 n 28253 n 22588 y 42449 y 21208 y 2971 n 9729 n 44813 n 11057 n 11667 n 5621 n 43233 y 37050 n 35620 n 31076 n 18342 y 8491 n 41815 y 34916 y 869 y 25077 n 31784 y 12975 y 24260 n 29619 y 22453 y 18893 y 44533 y 46108 y 297...
output:
Yes
result:
ok single line: 'Yes'