QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#416786#8512. Harmonic OperationskevinshanWA 3ms6976kbC++142.6kb2024-05-22 07:39:422024-05-22 07:39:43

Judging History

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

  • [2024-05-22 07:39:43]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:6976kb
  • [2024-05-22 07:39:42]
  • 提交

answer

//#pragma GCC optimize("O3")
// 1200

#include <bits/stdc++.h>
#include <random>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef vector<int> vi; 
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
#define bk back()
#define pb push_back

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define For(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define Rof(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7;
const ld PI = acos((ld)-1);
mt19937 rng; // or mt19937_64
template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }

void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << h; if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

#define vl vector<ll>

const int MX = 4e5+5;
ll p=97;
ll pows[MX];

vl hashstr(string S) {
	vl hsh(sz(S)+1);
	For(i,sz(S)) {
		hsh[i+1] = (hsh[i]+(S[i]-'a'+1)*pows[i])%MOD;
	}
	return hsh;
}
void solve() {
	string S;cin>>S;
	int n = sz(S);
	string S2 = S+S;
	pows[0] = 1;
	FOR(i,1,MX) pows[i] = pows[i-1]*p%MOD;

	vector<vl> hsh(2);
	hsh[0] = hashstr(S2);
	reverse(all(S2));
	hsh[1] = hashstr(S2);
	reverse(all(S2));

	map<ll, vpi> M;
	For(k,2) For(i,sz(S)) {
		ll tmp = hsh[k][n+i+1] - hsh[k][i];
		tmp = ((tmp%MOD)+MOD)%MOD;
		tmp = (tmp*pows[n-i])%MOD;
		M[tmp].pb({k,i});
	}

	vector<vl> gr(2, vl(n+1));
	int cnt = 1;
	trav(x,M) {
		dbg(x.f, sz(x.s));
		trav(y,x.s) {
			dbg(cnt,y.f,y.s);
			gr[y.f][y.s] = cnt;
		}
		cnt++;
	}


	int K; cin>>K;
	vpi pre(K+1);
	ll ans = 0;
	vi grCnt(cnt+5);
	grCnt[gr[0][0]]++;
	For(i,K) {
		char c;cin>>c;
		if(c=='I') {
			// pre[i+1] = {1^pre[i].f,-pre[i].s%n+n};
			pre[i+1] = {1^pre[i].f,pre[i].s%n+n};
		} else if(c=='R') {
			int x;cin>>x;
			pre[i+1] = {pre[i].f,(pre[i].s+x)%n};
		} else {
			int x;cin>>x;
			pre[i+1] = {pre[i].f,(pre[i].s-x)%n};
		}

		int grId = gr[pre[i+1].f][(pre[i+1].s%n+n)%n];
		dbg(i,grId, ans);
		ans += grCnt[grId];

		grCnt[grId]++;
	}
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	solve();
}


/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

pda
2
R 2
L 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

aaa
4
R 1
I
I
R 1

output:

10

result:

ok 1 number(s): "10"

Test #3:

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

input:

caso
6
L 1
I
I
R 1
I
I

output:

4

result:

ok 1 number(s): "4"

Test #4:

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

input:

qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq
100
L 12
I
R 47
L 54
I
I
R 80
L 86
L 19
R 5
L 53
L 40
R 20
L 11
R 40
I
I
R 66
R 6
L 76
L 93
R 39
I
I
L 24
R 59
R 99
L 52
I
I
R 77
L 11
R 60
L 16
I
L 40
I
R 35
L 64
R 11
L 34
I
R 35
I
L 87
I
I
L 42
L ...

output:

5050

result:

ok 1 number(s): "5050"

Test #5:

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

input:

wewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewe
100
R 83
R 34
I
I
R 87
R 74
L 98
I
L 77
L 8
R 23
L 94
I
I
L 79
L 87
L 47
L 85
L 49
L 7
I
I
R 97
R 15
I
R 66
L 8
R 62
R 68
I
I
R 32
R 24
R 36
L 60
R 75
R 77
I
L 42
I
L 61
I
I
R 78
R 51
L 98
I
L 77
I
I...

output:

2556

result:

ok 1 number(s): "2556"

Test #6:

score: -100
Wrong Answer
time: 2ms
memory: 6724kb

input:

rtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtr
100
R 27
R 68
I
L 29
L 51
L 19
L 12
L 10
L 52
L 38
L 17
R 30
L 29
L 51
L 17
R 29
I
R 96
R 50
R 56
I
I
I
L 73
L 15
I
R 1
R 81
L 94
R 27
R 52
R 57
R 44
I
I
L 53
I
R 87
L 39
L 25
I
I
R 25
I
I
I
L 88
L ...

output:

118

result:

wrong answer 1st numbers differ - expected: '116', found: '118'