QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #300689 | #7857. (-1,1)-Sumplete | willow# | Compile Error | / | / | C++14 | 5.3kb | 2024-01-08 17:07:56 | 2024-01-08 17:07:56 |
Judging History
answer
111
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int Add(int x, int y) {
return (x += y) >= mod ? x - mod : x;
}
int Sub(int x, int y) {
return (x -= y) < 0 ? x + mod : x;
}
int Mul(int x, int y) {
return 1ll * x * y % mod;
}
string eq[15][2], e;
int n, tot;
struct Dsu {
int fa[26], can[26];
void Init() {
for(int i = 0; i < 26; ++ i)
fa[i] = i, can[i] = (1 << 10) - 1;
}
int Get(int x) {
return x == fa[x] ? x : fa[x] = Get(fa[x]);
}
int Set(int id, int l, int r) {
int p = Get(id), to = 0;
for(int i = l; i <= r; ++ i)
to |= 1 << i;
can[p] &= to;
return can[p];
}
int Merge(int u, int v) {
int x = Get(u), y = Get(v);
if(x == y)
return 1;
fa[y] = x;
can[x] &= can[y];
return can[x];
}
}d;
int ans, clk, to[26][26], deg[26], out[26], ways[26][10];
vector<int> G[26];
queue<int>q;
void Calc(Dsu &now, vector<vector<int> > &less) {
cerr << "One Calc: ";
for(int i = 0; i < 26; ++ i) {
cerr << char(now.Get(i) + 'A') << " ";
}
cerr << endl;
for(int i = 0; i < 26; ++ i) {
if(now.Get(i) == i) {
cerr << "letter " << char(i + 'A') << ": ";
for(int j = 0; j < 10; ++ j)
cerr << (now.can[i] >> j & 1);
cerr << endl;
}
}
++ clk;
for(int i = 0; i < 26; ++ i) {
deg[i] = out[i] = 0;
fill(ways[i], ways[i] + 10, 0);
for(int j = 0; j < 10; ++ j) {
if(now.can[i] >> j & 1) {
ways[i][j] = 1;
}
}
G[i].clear();
for(auto v : less[i]) {
int x = now.Get(i), y = now.Get(v);
if(x == y)
return;
if(to[x][y] != clk) {
to[x][y] = clk;
cerr << "Constraint: " << char(x + 'A') << " < " << char(y + 'A') << endl;
G[x].push_back(y);
++ deg[y];
out[x] = 1;
}
}
}
for(int i = 0; i < 26; ++ i) {
if(now.Get(i) != i) {
continue;
}
if(deg[i]) {
continue;
}
q.push(i);
}
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto v : G[u]) {
int pre = 0;
for(int j = 0; j < 10; ++ j) {
if(now.can[j]) {
ways[v][j] = Mul(ways[v][j], pre);
}
pre = Add(pre, ways[u][j]);
}
if(!(-- deg[v])) {
q.push(v);
}
}
}
int tot = 1;
for(int i = 0; i < 26; ++ i) {
if(!out[i] && now.Get(i) == i) {
cerr << "Ways of Letter " << char(i + 'A') << ": ";
int sum = 0;
for(int j = 0; j < 10; ++ j) {
cerr << ways[i][j] << " ";
sum = Add(sum, ways[i][j]);
}
cerr << "sum = " << sum << endl;
tot = Mul(tot, sum);
}
}
cerr << tot << endl;
ans = Add(ans, tot);
}
void Solve(int pos, Dsu now, vector<vector<int> > less) {
if(pos == tot) {
Calc(now, less);
return;
}
int len = eq[pos][0].length();
for(int i = 0; i < len; ++ i) {
Dsu nxt = now;
if(isdigit(eq[pos][0][i]) && isdigit(eq[pos][1][i])) {
int l = eq[pos][0][i] - '0', r = eq[pos][1][i] - '0';
if(l > r)
break;
if(l < r)
Solve(pos + 1, nxt, less);
if(eq[pos][0][i] != eq[pos][1][i]) {
break;
}
}
if(isdigit(eq[pos][0][i])) {
int l = eq[pos][0][i] - '0', r = eq[pos][1][i] - 'A';
if(nxt.Set(r, l + 1, 9))
Solve(pos + 1, nxt, less);
if(!now.Set(r, l, l))
break;
continue;
}
if(isdigit(eq[pos][1][i])) {
int l = eq[pos][0][i] - 'A', r = eq[pos][1][i] - '0';
if(nxt.Set(l, 0, r - 1))
Solve(pos + 1, nxt, less);
if(!now.Set(l, r, r))
break;
continue;
}
int l = eq[pos][0][i] - 'A', r = eq[pos][1][i] - 'A';
cerr << eq[pos][0][i] << " < " << eq[pos][1][i] << endl;
less[l].push_back(r);
Solve(pos + 1, nxt, less);
less[l].pop_back();
if(!now.Merge(l, r))
break;
}
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
d.Init();
for(int i = 1; i <= n; ++ i) {
cin >> e;
string lef = "", rig = "";
int len = e.length(), pos = -1;
for(int j = 0; j < len; ++ j) {
if(e[j] == '=' || e[j] == '>' || e[j] == '<') {
pos = j;
break;
}
}
for(int j = 0; j < pos; ++ j)
lef += e[j];
for(int j = pos + 1; j < len; ++ j)
rig += e[j];
if(e[pos] == '=') {
while(lef.length() < rig.length())
lef = '0' + lef;
while(rig.length() < lef.length())
rig = '0' + rig;
int l = lef.length();
for(int j = 0; j < l; ++ j) {
if(isdigit(lef[j]) && isdigit(rig[j])) {
if(lef[j] != rig[j]) {
return 0 * puts("0");
}
continue;
}
if(isdigit(lef[j])) {
d.Set(rig[j] - 'A', lef[j] - '0', lef[j] - '0');
continue;
}
if(isdigit(rig[j])) {
d.Set(lef[j] - 'A', rig[j] - '0', rig[j] - '0');
continue;
}
d.Merge(lef[j] - 'A', rig[j] - 'A');
}
continue;
}
if(e[pos] == '>') {
swap(lef, rig);
}
if(rig.length() < lef.length()) {
int diff = lef.length() - rig.length();
for(int j = 0; j < diff; ++ j) {
if(!d.Set(lef[j] - 'A', 0, 0)) {
return 0 * puts("0");
}
}
string tmp = "";
for(int j = diff; j < (int)lef.length(); ++ j) {
tmp += lef[j];
}
lef = tmp;
assert(lef.length() == rig.length());
}
else {
while(lef.length() < rig.length()) {
lef = '0' + lef;
}
}
eq[tot][0] = lef;
eq[tot][1] = rig;
cerr << eq[tot][0] << " < " << eq[tot][1] << endl;
tot ++;
}
Solve(0, d, vector<vector<int> >(26, vector<int>()));
printf("%d\n", ans);
}
Details
answer.code:2:1: error: expected unqualified-id before numeric constant
2 | 111
| ^~~
In file included from /usr/include/c++/11/cmath:43,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
from answer.code:3:
/usr/include/c++/11/ext/type_traits.h:162:35: error: ‘bool __gnu_cxx::__is_null_pointer’ redeclared as different kind of entity
162 | __is_null_pointer(std::nullptr_t)
| ^
/usr/include/c++/11/ext/type_traits.h:157:5: note: previous declaration ‘template<class _Type> bool __gnu_cxx::__is_null_pointer(_Type)’
157 | __is_null_pointer(_Type)
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/11/ext/type_traits.h:162:26: error: ‘nullptr_t’ is not a member of ‘std’
162 | __is_null_pointer(std::nullptr_t)
| ^~~~~~~~~
In file included from /usr/include/c++/11/bits/exception_ptr.h:40,
from /usr/include/c++/11/exception:147,
from /usr/include/c++/11/ios:39,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:3:
/usr/include/c++/11/new:126:26: error: declaration of ‘operator new’ as non-function
126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
| ^~~~~~~~
/usr/include/c++/11/new:126:44: error: ‘size_t’ is not a member of ‘std’; did you mean ‘time_t’?
126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
| ^~~~~~
| time_t
/usr/include/c++/11/new:127:41: error: attributes after parenthesized initializer ignored [-fpermissive]
127 | __attribute__((__externally_visible__));
| ^
/usr/include/c++/11/new:128:26: error: declaration of ‘operator new []’ as non-function
128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
| ^~~~~~~~
/usr/include/c++/11/new:128:46: error: ‘size_t’ is not a member of ‘std’; did you mean ‘time_t’?
128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
| ^~~~~~
| time_t
/usr/include/c++/11/new:129:41: error: attributes after parenthesized initializer ignored [-fpermissive]
129 | __attribute__((__externally_visible__));
| ^
/usr/include/c++/11/new:135:34: error: ‘std::size_t’ has not been declared
135 | void operator delete(void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~
/usr/include/c++/11/new:137:36: error: ‘std::size_t’ has not been declared
137 | void operator delete[](void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~
/usr/include/c++/11/new:140:26: error: declaration of ‘operator new’ as non-function
140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~~~
/usr/include/c++/11/new:140:44: error: ‘size_t’ is not a member of ‘std’; did you mean ‘time_t’?
140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~
| time_t
/usr/include/c++/11/new:140:52: error: expected primary-expression before ‘const’
140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
| ^~~~~
/usr/include/c++/11/new:142:26: error: declaration of ‘operator new []’ as non-function
142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~~~
/usr/include/c++/11/new:142:46: error: ‘size_t’ is not a member of ‘std’; did you mean ‘time_t’?
142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
| ^~~~~~
| time_t
/usr/include/c++/11/new:142:54: error: expected primary-expression before ‘const’
142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
| ^~~~~
/usr/include/c++/11/new:174:33: error: declaration of ‘operator new’ as non-function
174 | _GLIBCXX_NODISCARD inline void* operator new(std::size_t, void* __p) _G...