Your title here...↵
------------------↵
↵
hi I got msgs from system that my solutions matches with some other people I was very curious so I check my solution and a solution of person from which my solution match according to system his user was byteplay_studios ↵
↵
his solution for C problem in edu round 174 ↵
↵
#include <iostream>↵
#include <vector>↵
using namespace std;↵
↵
const int MOD = 998244353;↵
↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
↵
↵
int maxExp = 200000 + 5;↵
vector<int> pow2(maxExp + 1, 0), inv2(maxExp + 1, 0);↵
pow2[0] = 1;↵
for (int i = 1; i <= maxExp; i++){↵
long long tmp = (long long) pow2[i - 1] * 2;↵
tmp %= MOD;↵
pow2[i] = (int) tmp;↵
}↵
↵
inv2[0] = 1;↵
const int invTwo = 499122177;↵
for (int i = 1; i <= maxExp; i++){↵
long long tmp = (long long) inv2[i - 1] * invTwo;↵
tmp %= MOD;↵
inv2[i] = (int) tmp;↵
}↵
↵
while(t--){↵
int n;↵
cin >> n;↵
vector<int> a(n + 1);↵
for (int i = 1; i <= n; i++){↵
cin >> a[i];↵
}↵
↵
↵
vector<int> P(n + 1, 0);↵
for (int i = 1; i <= n; i++){↵
P[i] = P[i - 1] + (a[i] == 2);↵
}↵
↵
↵
vector<int> suff(n + 2, 0);↵
for (int i = n; i >= 1; i--){↵
int addVal = 0;↵
if(a[i] == 3){↵
addVal = pow2[P[i - 1]];↵
}↵
suff[i] = (suff[i + 1] + addVal) % MOD;↵
}↵
↵
↵
vector<int> suffCount3(n + 2, 0);↵
for (int i = n; i >= 1; i--){↵
suffCount3[i] = suffCount3[i + 1] + (a[i] == 3);↵
}↵
↵
long long ans = 0;↵
↵
for (int i = 1; i <= n; i++){↵
if(a[i] == 1){↵
long long contribution = ((long long) suff[i + 1] * inv2[P[i]]) % MOD;↵
contribution = (contribution - suffCount3[i + 1]) % MOD;↵
if(contribution < 0)↵
contribution += MOD;↵
ans = (ans + contribution) % MOD;↵
}↵
}↵
↵
cout << ans % MOD << "\n";↵
}↵
return 0;↵
}↵
↵
My solution ↵
↵
#include <iostream>↵
#include <vector>↵
using namespace std;↵
↵
const int M = 998244353;↵
const int MX = 200005;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
↵
vector<long long> p(MX);↵
vector<long long> ip(MX);↵
↵
p[0] = 1;↵
for (int i = 1; i < MX; i++) {↵
p[i] = (p[i - 1] * 2LL) % M;↵
}↵
↵
const long long v = 499122177;↵
ip[0] = 1;↵
for (int i = 1; i < MX; i++) {↵
ip[i] = (ip[i - 1] * v) % M;↵
}↵
↵
while (t--) {↵
int n;↵
cin >> n;↵
vector<int> a(n);↵
↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
}↵
↵
long long r = 0;↵
long long s = 0;↵
int o = 0;↵
int w = 0;↵
↵
for (int i = 0; i < n; i++) {↵
if (a[i] == 1) {↵
s = (s + ip[w]) % M;↵
o++;↵
} ↵
else if (a[i] == 2) {↵
w++;↵
}↵
else if (a[i] == 3) {↵
long long c = ((p[w] * s) % M - o) % M;↵
if (c < 0) {↵
c += M;↵
}↵
r = (r + c) % M;↵
}↵
}↵
↵
cout << r << "\n";↵
}↵
↵
return 0;↵
}↵
↵
I think this is a bug or smt I want to say to [user:MikeMirzuhayanov],2025-02-24] plz reconsider the system desicion thsm
------------------↵
↵
hi I got msgs from system that my solutions matches with some other people I was very curious so I check my solution and a solution of person from which my solution match according to system his user was byteplay_studios ↵
↵
his solution for C problem in edu round 174 ↵
↵
#include <iostream>↵
#include <vector>↵
using namespace std;↵
↵
const int MOD = 998244353;↵
↵
int main(){↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
↵
↵
int maxExp = 200000 + 5;↵
vector<int> pow2(maxExp + 1, 0), inv2(maxExp + 1, 0);↵
pow2[0] = 1;↵
for (int i = 1; i <= maxExp; i++){↵
long long tmp = (long long) pow2[i - 1] * 2;↵
tmp %= MOD;↵
pow2[i] = (int) tmp;↵
}↵
↵
inv2[0] = 1;↵
const int invTwo = 499122177;↵
for (int i = 1; i <= maxExp; i++){↵
long long tmp = (long long) inv2[i - 1] * invTwo;↵
tmp %= MOD;↵
inv2[i] = (int) tmp;↵
}↵
↵
while(t--){↵
int n;↵
cin >> n;↵
vector<int> a(n + 1);↵
for (int i = 1; i <= n; i++){↵
cin >> a[i];↵
}↵
↵
↵
vector<int> P(n + 1, 0);↵
for (int i = 1; i <= n; i++){↵
P[i] = P[i - 1] + (a[i] == 2);↵
}↵
↵
↵
vector<int> suff(n + 2, 0);↵
for (int i = n; i >= 1; i--){↵
int addVal = 0;↵
if(a[i] == 3){↵
addVal = pow2[P[i - 1]];↵
}↵
suff[i] = (suff[i + 1] + addVal) % MOD;↵
}↵
↵
↵
vector<int> suffCount3(n + 2, 0);↵
for (int i = n; i >= 1; i--){↵
suffCount3[i] = suffCount3[i + 1] + (a[i] == 3);↵
}↵
↵
long long ans = 0;↵
↵
for (int i = 1; i <= n; i++){↵
if(a[i] == 1){↵
long long contribution = ((long long) suff[i + 1] * inv2[P[i]]) % MOD;↵
contribution = (contribution - suffCount3[i + 1]) % MOD;↵
if(contribution < 0)↵
contribution += MOD;↵
ans = (ans + contribution) % MOD;↵
}↵
}↵
↵
cout << ans % MOD << "\n";↵
}↵
return 0;↵
}↵
↵
My solution ↵
↵
#include <iostream>↵
#include <vector>↵
using namespace std;↵
↵
const int M = 998244353;↵
const int MX = 200005;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
↵
vector<long long> p(MX);↵
vector<long long> ip(MX);↵
↵
p[0] = 1;↵
for (int i = 1; i < MX; i++) {↵
p[i] = (p[i - 1] * 2LL) % M;↵
}↵
↵
const long long v = 499122177;↵
ip[0] = 1;↵
for (int i = 1; i < MX; i++) {↵
ip[i] = (ip[i - 1] * v) % M;↵
}↵
↵
while (t--) {↵
int n;↵
cin >> n;↵
vector<int> a(n);↵
↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
}↵
↵
long long r = 0;↵
long long s = 0;↵
int o = 0;↵
int w = 0;↵
↵
for (int i = 0; i < n; i++) {↵
if (a[i] == 1) {↵
s = (s + ip[w]) % M;↵
o++;↵
} ↵
else if (a[i] == 2) {↵
w++;↵
}↵
else if (a[i] == 3) {↵
long long c = ((p[w] * s) % M - o) % M;↵
if (c < 0) {↵
c += M;↵
}↵
r = (r + c) % M;↵
}↵
}↵
↵
cout << r << "\n";↵
}↵
↵
return 0;↵
}↵
↵
I think this is a bug or smt I want to say to [user:MikeMirz
