Submission #528651

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
528651	2022-02-21T01:27:29 Z	colazcy	Slon (COCI15_slon)	C++17	120 / 120	3 ms	1732 KB

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{(k - rhs.k + mod) % mod,(b - rhs.b + mod) % 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 : )
	// 5 : (
};

int pri(const int id){
	if(id == 0)return 0;
	if(id == 1)return 1;
	if(id == 2 || id == 3)return 2;
	if(id == 4)return 4;
	if(id == 5)return 5;
	assert(false);
}
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 if(str[l] == '(')seq.push_back(Token{5});
				else assert(false);
			}
		}();
		std::stack<Token> stk;
		for(let x : seq)
			if(x.id == 5)stk.push(x);
			else{
				if(x.id == 4){
					while(stk.top().id != 5){
						expr.push_back(stk.top());
						stk.pop();
					}
					stk.pop();
				}else{
					while(!stk.empty() && pri(stk.top().id) < pri(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 b = stk.top(); stk.pop();
		assert(!stk.empty());
		let a = stk.top(); stk.pop();
		stk.push(a * b);
	}else if(x.id == 2){
		assert(!stk.empty());
		let b = stk.top(); stk.pop();
		assert(!stk.empty());
		let a = stk.top(); stk.pop();
		stk.push(a + b);		
	}else if(x.id == 3){
		assert(!stk.empty());
		let b = stk.top(); stk.pop();
		assert(!stk.empty());
		let a = stk.top(); stk.pop();
		stk.push(a - b);		
	}else assert(false);
	assert(!stk.empty());
	return stk.top();
}
int main(){
	// std::freopen("slon.in.1","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

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

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	3 ms	1732 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	0 ms	460 KB	Output is correct
8	Correct	1 ms	780 KB	Output is correct
9	Correct	1 ms	780 KB	Output is correct
10	Correct	2 ms	1224 KB	Output is correct