QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#726636#3619. Restroom Monitornickbelov#AC ✓29ms8344kbC++202.8kb2024-11-09 04:34:022024-11-09 04:34:02

Judging History

This is the latest submission verdict.

  • [2024-11-09 04:34:02]
  • Judged
  • Verdict: AC
  • Time: 29ms
  • Memory: 8344kb
  • [2024-11-09 04:34:02]
  • Submitted

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'