| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 622468 |
2022-08-04T10:00:16 Z |
inksamurai |
Slon (COCI15_slon) |
C++17 |
|
4 ms |
468 KB |
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3SgiE60 ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class ...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
int binpow(int a,int b,int mod){
int res=1;
while(b){
if(b%2){
res=res*a%mod;
res%=mod;
}
a=a*a%mod;
a%=mod;
b/=2;
}
return res;
}
signed main(){
_3SgiE60;
string s;
cin>>s;
int need,mod;
cin>>need>>mod;
const int n=sz(s);
// k*x+l
auto digit=[&](char ch)->bool{
return ch>='0' and ch<='9';
};
auto operation=[&](char ch)->bool{
return ch=='+' or ch=='-' or ch=='*';
};
auto _get_id=[&](char ch)->int{
return ch=='+'?0:ch=='-'?1:2;
};
auto merge=[&](pii p,pii q,int t)->pii{
// print(t);
pii res;
if(t==2){
res.fi=p.fi*q.fi+p.fi*q.se%mod;
res.fi+=p.se*q.fi%mod;
res.se=p.se*q.se%mod;
}else if(t==1){
res.fi=(p.fi-q.fi+mod*mod)%mod;
res.se=(p.se-q.se+mod*mod)%mod;
}else if(t==0){
res.fi=(p.fi+q.fi)%mod;
res.se=(p.se+q.se)%mod;
}
res.fi%=mod;
res.se%=mod;
return res;
};
using T=pair<int,pii>;
int i=0;
auto dfs=[&](auto self)->pii{
if(i>=n) return {0,0};
int pi=i;
vec(T) ops;
// type,val
while(i<n){
if(s[i]=='('){
i+=1;
pii np=self(self);
// if(pi==0) print(i,np.fi,np.se);
ops.pb(T(1,np));
}else if(s[i]==')'){
i+=1;
break;
}else{
if(operation(s[i])){
ops.pb(T(0,pii(_get_id(s[i]),0)));
i+=1;
}else{
pii np={0,0};
if(s[i]=='x'){
np={1,0};
i+=1;
}else{
int v=0;
while(digit(s[i])){
v=v*10+(s[i]-'0');
v%=mod;
i+=1;
}
np={0,v};
}
ops.pb(T(1,np));
}
}
}
// if(pi==0){
// for(auto tp:ops){
// print(tp.fi,tp.se.fi,tp.se.se);
// }
// }
vec(T) nops;
rep(_i,sz(ops)){
if(ops[_i].fi==0 and ops[_i].se.fi==2){
assert(_i and _i<sz(ops)-1 and ops[_i-1].fi==1);
pii p=ops[_i-1].se;
for(int j=_i;j<sz(ops);j+=2){
if(ops[j].se.fi!=2){
break;
}
p=merge(p,ops[j+1].se,2);
_i=j+1;
}
nops.pb(T(1,p));
}else if(_i==sz(ops)-1 or !(ops[_i+1].fi==0 and ops[_i+1].se.fi==2)){
nops.pb(ops[_i]);
}
}
// print("\n..... old operations ");
// for(auto tp:ops){
// print(tp.fi,tp.se.fi,tp.se.se);
// }
// print("\n.......");
ops=nops;
if(sz(ops)==1) return ops[0].se;
if(!sz(ops)) return {0,0};
assert(ops[0].fi==1);
pii p=ops[0].se;
for(int _i=2;_i<sz(ops);_i+=2){
// print("ho",ops[i-1].se.fi);
assert(ops[_i-1].fi==0);
p=merge(p,ops[_i].se,ops[_i-1].se.fi);
}
// if(i==0){
// print(p.fi,p.se);
// }
// pii p={0,0};
return p;
};
pii p=dfs(dfs);
// print(p.fi,p.se);
for(int i=0;i<mod;i++){
if((p.fi*i+p.se)%mod==need){
cout<<i<<"\n";
return 0;
}
}
}
Compilation message
slon.cpp: In instantiation of 'main()::<lambda(auto:23)> [with auto:23 = main()::<lambda(auto:23)>; pii = std::pair<long long int, long long int>]':
slon.cpp:149:15: required from here
slon.cpp:72:7: warning: unused variable 'pi' [-Wunused-variable]
72 | int pi=i;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
212 KB |
Output is correct |
| 2 |
Correct |
4 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
3 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
2 ms |
340 KB |
Output is correct |
| 10 |
Correct |
2 ms |
340 KB |
Output is correct |
