| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 255744 |
2020-08-01T19:09:13 Z |
Vimmer |
Slon (COCI15_slon) |
C++14 |
|
1000 ms |
640 KB |
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define pf push_front
#define N 100050
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9
using namespace std;
//using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef short int si;
typedef array <ll, 3> a3;
typedef array <ll, 5> a5;
//typedef tree <ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
string a;
ll p, m;
ll sm(ll x, ll y) {return (x + y) % m;}
ll mult(ll x, ll y) {return (x * y) % m;}
bool gd(int x) {return a[x] != '+' && a[x] != '-' && a[x] != '*' && a[x] != '(' && a[x] != ')';}
pair <pair <ll, ll>, int> calc(int v)
{
ll kf = 0, val = 0, otr = 1;
for (int i = v + 1; i < sz(a); i++)
{
if (a[i] == ')') return {{val, kf}, i + 1};
if (a[i] == '(')
{
pair <pair <ll, ll>, int> pt = calc(i);
i = pt.S;
if (a[i] != '*')
{
val = sm(val, mult(otr, pt.F.F));
kf = sm(kf, mult(otr, pt.F.S));
i--;
continue;
}
else
{
ll cur = max(1ll, pt.F.F), kft = 0, from = 1, dob = 0;
if (pt.F.S != 0) kft = pt.F.S;
else from = cur;
i++;
while (1)
{
if (a[i] == '(')
{
pair <pair <ll, ll>, int> pt = calc(i);
if (pt.F.S == 0) from = mult(from, pt.F.F);
if (pt.F.S != 0) kft = pt.F.S;
if (pt.F.F != 0) {if (kft == 0 || pt.F.S != 0) dob = 1; cur = mult(cur, pt.F.F);}
i = pt.S;
if (a[i] == '*') {i++; continue;}
kft = mult(kft, from);
kf = sm(kf, mult(kft, otr));
if (kft == 0) val = sm(val, mult(cur, otr));
else
val = sm(val, mult(dob, mult(cur, otr)));
if (a[i] == '+') otr = 1;
if (a[i] == '-') otr = -1;
if (a[i] == ')') return {{val, kf}, i + 1};
break;
}
ll num = 0, j = 0;
while (i + j + 1 < sz(a) && gd(i + j + 1)) j++;
for (int u = i; u <= i + j; u++) {num *= 10; num += a[u] - '0'; num = sm(num, 0);}
if (j == 0 && a[i + j] == 'x') num = -1;
if (num == -1) {kft = 1;}else {from = mult(from, num); cur = mult(cur, num);}
i += j + 1;
if (a[i] == '*') {i++; continue;}
kft = mult(from, kft);
kf = sm(kf, mult(kft, otr));
if (kft == 0) val = sm(val, mult(cur, otr));
else
val = sm(val, mult(dob, mult(cur, otr)));
if (a[i] == '+') otr = 1;
if (a[i] == '-') otr = -1;
if (a[i] == ')') return {{val, kf}, i + 1};
break;
}
}
continue;
}
if (a[i] == '+') {otr = 1; continue;}
if (a[i] == '-') {otr = -1; continue;}
int j = 0;
ll num = 0;
while (i + j + 1 < sz(a) && gd(i + j + 1)) j++;
for (int u = i; u <= i + j; u++) {num *= 10; num += a[u] - '0'; num = sm(num, 0);}
if (j == 0 && a[i + j] == 'x') num = -1;
i += j + 1;
if (a[i] == '+') {if (num != -1) val = sm(val, mult(otr, num)); else kf = sm(kf, otr); otr = 1; continue;}
if (a[i] == '-') {if (num != -1) val = sm(val, mult(otr, num)); else kf = sm(kf, otr); otr = -1; continue;}
if (a[i] == ')')
{
if (num == -1) kf = sm(kf, otr);
else val = sm(val, mult(otr, num));
return {{val, kf}, i + 1};
}
{
ll cur = 1, kft = 0, from = 1, dob = 0;
if (num != -1)
{
from = mult(from, num); cur = num;} else kft = 1;
i++;
while (1)
{
if (a[i] == '(')
{
pair <pair <ll, ll>, int> pt = calc(i);
if (pt.F.S == 0) from = mult(from, pt.F.F);
if (pt.F.S != 0) kft = pt.F.S;
if (pt.F.F != 0) {if (kft == 0 || pt.F.S != 0) dob = 1; cur = mult(cur, pt.F.F);}
i = pt.S;
if (a[i] == '*') {i++; continue;}
kft = mult(kft, from);
kf = sm(kf, mult(kft, otr));
if (kft == 0) val = sm(val, mult(cur, otr));
else
val = sm(val, mult(dob, mult(cur, otr)));
if (a[i] == '+') otr = 1;
if (a[i] == '-') otr = -1;
if (a[i] == ')') return {{val, kf}, i + 1};
break;
}
ll num = 0, j = 0;
while (i + j + 1 < sz(a) && gd(i + j + 1)) j++;
for (int u = i; u <= i + j; u++) {num *= 10; num += a[u] - '0'; num = sm(num, 0);}
if (j == 0 && a[i + j] == 'x') num = -1;
if (num == -1)
{
kft = 1;
} else {cur = mult(cur, num); from = mult(from, num);}
i += j + 1;
if (a[i] == '*') {i++; continue;}
kft = mult(kft, from);
kf = sm(kf, mult(kft, otr));
if (kft == 0) val = sm(val, mult(cur, otr));
else
val = sm(val, mult(dob, mult(cur, otr)));
if (a[i] == '+') otr = 1;
if (a[i] == '-') otr = -1;
if (a[i] == ')') return {{val, kf}, i + 1};
break;
}
}
}
}
int main()
{
//freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> a;
cin >> p >> m;
a = '(' + a;
a = a + ')';
pair <pair <ll, ll>, int> pt = calc(0);
ll val = pt.F.F, kf = pt.F.S;
p -= val;
p = sm(p, m);
ll x = 0;
while (1)
{
if ((x * kf + val) % m == p) {cout << x << endl; exit(0);}
x++;
}
}
Compilation message
slon.cpp: In function 'std::pair<std::pair<long long int, long long int>, int> calc(int)':
slon.cpp:250:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Execution timed out |
1084 ms |
636 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1095 ms |
384 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1096 ms |
384 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1093 ms |
384 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1093 ms |
384 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1099 ms |
384 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1086 ms |
384 KB |
Time limit exceeded |
| 9 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
640 KB |
Output isn't correct |
