QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#785045#7717. BitsetslyccRE 53ms31216kbC++202.6kb2024-11-26 16:42:382024-11-26 16:42:39

Judging History

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

  • [2024-11-26 16:42:39]
  • 评测
  • 测评结果:RE
  • 用时:53ms
  • 内存:31216kb
  • [2024-11-26 16:42:38]
  • 提交

answer

// Author: lycc
// 
// Problem: A. 【NOIP Round #8】位集
// Contest: Public Judge - Public NOIP Round #8 (Div. 1, 提高)
// URL: https://pjudge.ac/contest/1847/problem/21861
// Memory Limit: 1024 MB
// Time Limit: 1000 ms

#include <bits/stdc++.h>
#define int long long
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define pb emplace_back
#define For(i, x, y) for (int i = (x); i <= (y); i ++)
#define rep(i, x, y) for (int i = (x); i >= (y); i --)
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define sz(v) (int)((v).size())
#define ull unsigned long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mp make_pair
#define i128 __int128
#define db long double
#define vi vector< int >
#define mem(v, x) memset(v, x, sizeof(v))
#define A3 array< int, 3 >
#define A4 array< int, 4 >
#define vpii vector< pair< int, int > >
using namespace std;
mt19937_64 rnd(time(0));
template< typename T > void cmin(T &x, T y) { return x = min(x, y), void(); }
template< typename T > void cmax(T &x, T y) { return x = max(x, y), void(); }
int ksm(int x, int y, int p) {
    int v = 1; x %= p;
    while (y) v = 1ll * v * ((y & 1) ? x : 1) % p, x = 1ll * x * x % p, y >>= 1;
    return (v % p + p) % p;
}
void file() {
	freopen("1.in", "r", stdin);
	freopen("1.out", "w", stdout);
	return;
}
bool MemoryST;
const int N = 2e6 + 5;
const int mod = 998244353;
const long long INF = 1e18;
const int base = 13131;
int n, m, q, x, y, z;
int a[N], b[N];
string s, t;
vi f, g;
vi pos[N]; 
void Main() {
	cin >> n >> m;
	f.resize(m + 1); g.resize(m + 1);
	int lst = 0;
	For (i, 1, n) {
		cin >> s; s = " " + s;
		if (i == 1) {
			For (j, 1, m) f[j] = 1;
		} else {
			For (j, 1, m) {
				if (s[j] == t[j]) f[j] = g[j];
				else f[j] = i;
			}
		}
		For (j, 1, m) pos[i].pb(f[j]);
		sort(all(pos[i]));
		swap(s, t);
		swap(f, g);
	}
	cin >> q >> x >> y >> z;
	int ans = 0;
	For (i, 1, q) {
		if (i == 1) a[i] = 1, b[i] = n;
		else a[i] = (a[i - 1] * x + lst * y + z) % n + 1, b[i] = (b[i - 1] * y + lst * z + x) % n + 1;
		int l = min(a[i], b[i]), r = max(a[i], b[i]);
		ans += (lst = (ub(all(pos[r]), l) - pos[r].begin()));
	}
	cout << ans;
    return;
}
bool MemoryED;
signed main() {
	// file();
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cerr << fixed << setprecision(6) << (&MemoryST - &MemoryED) / 1048576.0 << "MB\n";
    int TESTCNT = 1;
    // cin >> TESTCNT;
    while (TESTCNT --) Main();
    cerr << endl << 1e3 * clock() / CLOCKS_PER_SEC << "ms"; 
    return 0;
}

详细

Test #1:

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

input:

4 10
1010110101
0101111001
1101101101
1011010000
4
10 5 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 3ms
memory: 6032kb

input:

6 3
110
011
010
100
101
111
5
7 5 5

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: 0
Accepted
time: 3ms
memory: 5984kb

input:

10 10
1100101001
0011100101
1100001110
0101011100
1001011010
0010101101
1001011011
0010110000
1001100111
0010101000
10
11 11 11

output:

26

result:

ok 1 number(s): "26"

Test #4:

score: 0
Accepted
time: 3ms
memory: 5932kb

input:

6 7
1101001
1000110
0010000
1110001
1110100
0001011
15
7 5 7

output:

30

result:

ok 1 number(s): "30"

Test #5:

score: 0
Accepted
time: 3ms
memory: 6064kb

input:

10 13
0101011101010
0100000011001
0001101010111
1101000111100
1001110000110
0110011000110
1101101110100
0101101110011
0000100011100
1100010110100
20
11 11 11

output:

60

result:

ok 1 number(s): "60"

Test #6:

score: 0
Accepted
time: 3ms
memory: 6128kb

input:

12 15
010010101101011
010000100100011
110011010100011
111011101010111
101110111010100
100000111011011
010100001101100
001011010111100
000011011100010
101100101001010
010000111101111
110100011011000
25
11 13 13

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 3ms
memory: 5936kb

input:

15 16
1111010001110110
1111100101111111
1111111111001010
0010100111111001
1011011000001000
1111000101000000
1001101100100011
0010111000001110
0011111000010001
1000011111011111
1101000111000001
0010010100001011
1110001111111010
0011100110100001
0101110010101101
30
13 13 17

output:

448

result:

ok 1 number(s): "448"

Test #8:

score: 0
Accepted
time: 3ms
memory: 5944kb

input:

13 15
001100110010010
011100110100111
111100000000110
111000011101010
111100011001010
100111101001001
000110010111101
100101000000100
011010001000000
101001100011100
011110111111000
010110111100111
110010010100110
35
13 13 11

output:

0

result:

ok 1 number(s): "0"

Test #9:

score: 0
Accepted
time: 0ms
memory: 5932kb

input:

11 9
110101001
001010011
000100101
110011000
110101110
001001100
110100110
100110000
100010111
110110000
111100000
40
13 11 13

output:

47

result:

ok 1 number(s): "47"

Test #10:

score: 0
Accepted
time: 2ms
memory: 5972kb

input:

10 18
010111010010010001
111010101000100111
011010111100011001
000010000111001111
101010010000110100
001110000101111101
010101011011000100
111011110001010010
111010101101000000
100101010111101100
45
11 11 11

output:

353

result:

ok 1 number(s): "353"

Test #11:

score: 0
Accepted
time: 2ms
memory: 5932kb

input:

11 17
01100000011010100
11100001111000101
10011100111011011
10011110010011000
10110110111110010
01001001101111000
11010101101101110
01101101110001110
11101000000101001
00000110000001000
10001111001100010
50
13 11 13

output:

228

result:

ok 1 number(s): "228"

Test #12:

score: 0
Accepted
time: 3ms
memory: 5872kb

input:

1 1
0
1
2 2 2

output:

1

result:

ok 1 number(s): "1"

Test #13:

score: 0
Accepted
time: 2ms
memory: 5852kb

input:

1 10
0010001000
1
2 2 2

output:

10

result:

ok 1 number(s): "10"

Test #14:

score: 0
Accepted
time: 3ms
memory: 5812kb

input:

10 1
0
0
0
0
1
0
0
0
1
0
1
11 11 11

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 3ms
memory: 6156kb

input:

100 100
0001000000000000100100100100000000100100100010000000000000000000000010000000000010001000000000000000
0000000000000000000000000000000000000000000000000000000000100000010000000010001000000100001000000000
000000000000000000000000000001000000010001000000000000000000000000000000100000000000001000...

output:

709

result:

ok 1 number(s): "709"

Test #16:

score: 0
Accepted
time: 11ms
memory: 7784kb

input:

500 500
1011111111111111111111111111011111110111111101111111111111111111111101111111111111111111111111111111011111111111111101111110101111111111111111101111111111111101110101111111110111111101111111111110111100111111101111111101011111111111111111111111111111111111111011111101111111111111111111111111...

output:

1394

result:

ok 1 number(s): "1394"

Test #17:

score: 0
Accepted
time: 36ms
memory: 13824kb

input:

1000 1000
00000000000000000000000000010000001110000000001000000100000000000000000000000000000000000001000000001000000000000000000000000000000000100010000000000000000000000000000000100000100100100100000000000000000000000000001100000000000001100000000000000000000000000000010000100000000000010000000000...

output:

21974

result:

ok 1 number(s): "21974"

Test #18:

score: 0
Accepted
time: 30ms
memory: 16508kb

input:

10000 100
1110111111110111111111111111111111011111111111011111111011111111111011111111111111111101111111111111
1110111101111111111111111111111111111111110111111111111111111111011111111101111111111111111111111111
1111110111111111111111111111011111111111111111111111111111111111111111111101111111111111...

output:

3586

result:

ok 1 number(s): "3586"

Test #19:

score: 0
Accepted
time: 23ms
memory: 14224kb

input:

100 10000
00110000010011110000100010110001110000001000010010110100001100010000011100100001111000000010000001000100101001000000010101001100000010100011011001000101001110000100100100100110000111010100000000101000001100011001101101011000010001110110000010010000000000000011101101100010110010100111000011...

output:

1046213

result:

ok 1 number(s): "1046213"

Test #20:

score: 0
Accepted
time: 34ms
memory: 18764kb

input:

5000 200
11000000100100000000000010001000000000000000000000000000010000000000000000000001000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000100000000000000000000000000010000000000000000000000010000000100000000000100000001000...

output:

170424

result:

ok 1 number(s): "170424"

Test #21:

score: 0
Accepted
time: 53ms
memory: 31216kb

input:

5000 200
00000000000000000000000000000000000000000000000000000000000000000000000000000000100000001000000000000000000000010010000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000100000000000000001000010000000000000000000100000001000000000001000000000100000000000010...

output:

2499626

result:

ok 1 number(s): "2499626"

Test #22:

score: -100
Runtime Error

input:

5000 200
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000010000100000000000
000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000...

output:


result: