Submission #622468

#	Time	Username	Problem	Language	Result	Execution time	Memory
622468		inksamurai	Slon (COCI15_slon)	C++17	120 / 120	4 ms	468 KiB

slon

#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 (stderr)

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;
      |       ^~

• Subtask 1: 120 / 120