Submission #528650

#	Time	Username	Problem	Language	Result	Execution time	Memory
528650		colazcy	Slon (COCI15_slon)	C++17	0 / 120	1 ms	588 KiB

slon

#include <cstdio>
#include <cassert>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
#include <stack>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_LIM = lim,REPN = 1;REPN <= REPN_LIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("Line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
constexpr int maxn = 1e5 + 100;

ll exgcd(const ll a,const ll b,ll &x,ll &y){
	if(!b){
		x = 1,y = 0;
		return a;
	}
	let res = exgcd(b,a % b,y,x);
	y -= (a / b) * x;
	return res;
}

char str[maxn];
int p,mod,n;
struct poly{
	int k,b;
	poly operator + (const poly &rhs)const{
		return poly{(k + rhs.k) % mod,(b + rhs.b) % mod};
	}
	poly operator * (const poly &rhs)const{
		return poly{int((1ll * k * rhs.b + 1ll * b * rhs.k) % mod),int(1ll * b * rhs.b % mod)};
	}
	void print()const{
		debug("%dx + %d\n",k,b);
	}
};


struct Token{
	int id;
	poly v;
	// 0 : poly
	// 1 : *
	// 2 : +
	// 3 : )
	// 4 : (
};

poly resolve(){
	std::vector<Token> expr;
	[&expr](){
		std::vector<Token> seq;
		[&seq](){
			for(int l = 1,r;l <= n;l = r + 1){
				r = l;
				if(std::isdigit(str[l]) || str[l] == 'x'){
					if(str[l] == 'x')seq.push_back(Token{0,poly{1,0}});
					else{	
						int s = str[l] - '0';
						while(std::isdigit(str[r + 1]))s = (s * 10 + str[++r] - '0') % mod;
						seq.push_back(Token{0,poly{0,s}});
					}
				}else if(str[l] == '*')seq.push_back(Token{1});
				else if(str[l] == '+')seq.push_back(Token{2});
				else if(str[l] == ')')seq.push_back(Token{3});
				else if(str[l] == '(')seq.push_back(Token{4});
				else assert(false);
			}
		}();
		std::stack<Token> stk;
		for(let x : seq)
			if(x.id == 4)stk.push(x);
			else{
				if(x.id == 3){
					while(stk.top().id != 4){
						expr.push_back(stk.top());
						stk.pop();
					}
					stk.pop();
				}else{
					while(!stk.empty() && stk.top().id < x.id){
						expr.push_back(stk.top());
						stk.pop();
					}
					stk.push(x);
				}
			}
		while(!stk.empty())expr.push_back(stk.top()),stk.pop();
	}();

	for(let t : expr)debug("%d (%d,%d)\n",t.id,t.v.k,t.v.b);
	std::stack<poly> stk;

	for(let x : expr)
	if(x.id == 0)stk.push(x.v);
	else if(x.id == 1){
		assert(!stk.empty());
		let a = stk.top(); stk.pop();
		assert(!stk.empty());
		let b = stk.top(); stk.pop();
		stk.push(a * b);
	}else if(x.id == 2){
		assert(!stk.empty());
		let a = stk.top(); stk.pop();
		assert(!stk.empty());
		let b = stk.top(); stk.pop();
		stk.push(a + b);		
	}else assert(false);
	assert(!stk.empty());
	return stk.top();
}
int main(){
	// std::freopen("slon.in","r",stdin);
	// std::freopen("slon.out","w",stdout);
	std::scanf("%s",str + 1);
	std::scanf("%d %d",&p,&mod);
	n = std::strlen(str + 1);
	let f = resolve();
	f.print();
	let k = f.k,b = f.b;
	ll x,t;
	let g = exgcd(k,mod,x,t);
	assert((p - b) % g == 0);
	x *= (p - b) / g;
	let m = std::abs(mod / g);
	x %= m;
	x += m;
	x %= m;
	std::printf("%lld\n",x);
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}

Compilation message (stderr)

slon.cpp: In function 'int main()':
slon.cpp:119:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |  std::scanf("%s",str + 1);
      |  ~~~~~~~~~~^~~~~~~~~~~~~~
slon.cpp:120:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |  std::scanf("%d %d",&p,&mod);
      |  ~~~~~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 120