#include using namespace std; #define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define __ freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); #define tr(...) cout<<__FUNCTION__<<' '<<__LINE__<<" = ";trace(#__VA_ARGS__, __VA_ARGS__) using namespace std; typedef long long ll; typedef long double ld; typedef pair pii; template ostream& operator<<(ostream& out,pair const& p){out<<'('< ostream& operator<<(ostream& out,vector const& v){ int l=v.size();for(int i=0;i0)out< void trace(const char* name, T&& arg1){cout< void trace(const char* names, T&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ',');cout.write(names, comma-names)<<" : "< adj[N * 2]; bool mark[N * 2]; inline bool dfs(int node) { if (mark[node ^ 1]) { return false; } if (mark[node]) { return true; } mark[node] = true; arr[id++] = node; for (int i = 0; i < (int) adj[node].size(); i++) { if (!dfs(adj[node][i])) { return false; } } return true; } inline void init() { for (int i = 0; i < NUM_VERTICES; i++) { adj[i].clear(); } memset(mark, 0, sizeof(mark)); } // Adds the clause (u or v) to the set of clauses inline void addOr(int u, int v) { adj[u ^ 1].push_back(v); adj[v ^ 1].push_back(u); } // Adds the clause (u == v) to the set of clauses inline void addEquivalent(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); adj[u ^ 1].push_back(v ^ 1); adj[v ^ 1].push_back(u ^ 1); } // Adds the clause (u xor v) to the set of clauses inline void addXor(int u, int v) { addOr(u, v); addOr(u ^ 1, v ^ 1); } // Forces variable (u) to be true inline void forceTrue(int u) { adj[u ^ 1].push_back(u); } // Forces variable (u) to be false inline void forceFalse(int u) { adj[u].push_back(u ^ 1); } // Adds the clause (u and v) to the set of clauses inline void addAnd(int u, int v) { forceTrue(u); forceTrue(v); } inline void addImplication(int u, int v) { adj[u].push_back(v); } // Returns true if a solution exists. inline bool solve() { for (int i = 0; i < NUM_VERTICES; i++) { sort(adj[i].begin(), adj[i].end()); adj[i].resize(unique(adj[i].begin(), adj[i].end()) - adj[i].begin()); } for (int i = 0; i < NUM_VERTICES; i += 2) { if ((!mark[i]) && (!mark[i + 1])) { id = 0; if(!dfs(i)) { while (id > 0) { mark[arr[--id]] = false; } if(!dfs(i + 1)) { return false; } } } } return true; } // End of 2-SAT Template. int check_in_between(int x, int L, int R) { return x >= L && x <= R; } struct Robot { int leftRange, rightRange; Robot(int a, int b): leftRange(a), rightRange(b) { } }; int can_robots_meet[10][10][10][10][2][2][20]; int isGood(Robot r, int startPos, int curPos) { if (curPos == startPos) return true; if (curPos < startPos) return startPos - curPos <= r.leftRange; else return curPos - startPos <= r.rightRange; } int FLAG = false; int canMeet(Robot a, Robot b, int firstDir, int secondDir, int d) { if (a.rightRange + b.leftRange < d) { return false; } const int ITERATIONS = 2000; int firstPos = a.leftRange; int secondPos = a.leftRange + d; int startPosFirst = firstPos; int startPosSecond = secondPos; for (int it = 0; it < ITERATIONS; it++) { if (a.leftRange > 0 || a.rightRange > 0) { firstPos += firstDir; if (!isGood(a, startPosFirst, firstPos)) { // || !check_in_between(firstPos, startPosFirst - a.leftRange, startPosFirst + a.rightRange)) { firstPos -= 2 * firstDir; firstDir *= -1; } } if (b.leftRange > 0 || b.rightRange > 0) { secondPos += secondDir; if (!isGood(b, startPosSecond, secondPos)) { //|| !check_in_between(secondPos, startPosSecond - b.leftRange, startPosSecond + b.rightRange)) { secondPos -= 2 * secondDir; secondDir *= -1; } } if (FLAG) { tr(firstPos, secondPos); tr(firstDir, secondDir); } if (firstPos == secondPos) { return true; } // cerr << "firstPos " << firstPos + 1 << " " << "secondPos" << " " << secondPos + 1 << endl; } return false; } void precompute() { int cnt = 0; for (int l1 = 0; l1 <= 9; l1++) { for (int r1 = 0; r1 <= 9; r1++) { for (int l2 = 0; l2 <= 9; l2++) { for (int r2 = 0; r2 <= 9; r2++) { for (int dir1 = -1; dir1 <= 1; dir1++) if (dir1 != 0) { for (int dir2 = -1; dir2 <= 1; dir2++) if (dir2 != 0) { for (int d = 1; d <= r1 + l2; d++) { cnt++; Robot a(l1, r1); Robot b(l2, r2); int ok = canMeet(a, b, dir1, dir2, d); can_robots_meet[l1][r1][l2][r2][dir1 == -1 ? 0 : 1][dir2 == -1 ? 0 : 1][d] = ok; // printf("cnt = %d, ok = %d\n", cnt, ok); } } } } } } } } int max_characters; void gen(string &s, vector &dir, int n) { // cerr << "here " << endl; if (s.size() == n) { return; } else { vector > possible; possible.push_back({'.', 0}); for (int ch = 1; ch < max_characters; ch++) { for (int dir2 = -1; dir2 <= 1; dir2++) if (dir2 != 0) { int ok = true; for (int delta = 1; delta < 20; delta++) { int i = (int) s.size() - delta; if (i >= 0) { if (s[i] == '.') { continue; } int l1 = min(s[i] - '0', i); int r1 = min(s[i] - '0', n - i - 1); int j = s.size(); int l2 = min(ch, j); int r2 = min(ch, n - j - 1); // tr(s, i, j, ch, l1, r1, l2, r2); int dir1 = dir[i]; int d1 = dir1 == -1 ? 0 : 1; int d2 = dir2 == -1 ? 0 : 1; // tr(can_robots_meet[l1][r1][l2][r2][d1][d2][j - i]); if (can_robots_meet[l1][r1][l2][r2][d1][d2][j - i]) { ok = false; break; } } } if (ok) { // tr(ch); possible.push_back({(char) ('0' + ch), dir2}); } } } // for (auto it: possible) { // cerr << it.first << " " << it.second << endl; // } // cerr << endl; // tr(possible); assert(possible.size()); int idx = 0; int temp = rand() % 5 + 1; for (int i = 0; i < temp; i++) { idx = max(idx, rand() % (int) possible.size()); } if (s.size() < 2 || rand() % 5 == 0) { idx = 0; } string &t = s; t += possible[idx].first; vector &newDir = dir; newDir.push_back(possible[idx].second); gen(t, newDir, n); } } int getNum(int L, int R) { if (L == R) return L; return L + rand() % (R - L + 1); } vector tests; void genGood(int S, int minN, int maxN) { int sz = 0; while (sz < S) { cerr << "sz " << sz << endl; max_characters = getNum(1, 9); if (minN > min(maxN, S - sz)) { minN = 1; } int n = getNum(minN, min(maxN, S - sz)); if (n == maxN && rand() % 2 == 0) { max_characters = 9; } // cerr << "n " << n << endl; string s = ""; vector v; gen(s, v, n); tests.push_back(s); sz += n; } } void genBad(int S, int minN, int maxN) { int sz = 0; while (sz < S) { max_characters = getNum(1, 9); if (minN > min(maxN, S - sz)) { minN = 1; } int n = getNum(minN, min(maxN, S - sz)); if (n == maxN) { max_characters = 9; } string s = ""; vector v; gen(s, v, n); int idx = getNum(0, s.size() - 1); s[idx] = (char) ('0' + getNum(0, 9)); tests.push_back(s); sz += n; } } int tc = 1; void addTests1() { string fileName = to_string(tc) + ".in"; freopen(fileName.c_str(), "w", stdout); tc++; tests.clear(); genGood(200, 1, 100); genBad(100, 1, 100); cout << tests.size() << endl; for (auto s: tests) { cout << s << endl; } } void addTests2() { string fileName = to_string(tc) + ".in"; freopen(fileName.c_str(), "w", stdout); tc++; int S = 300; tests.clear(); genGood(S, 100, 100); cout << tests.size() << endl; for (auto s: tests) { cout << s << endl; } } void addTests3() { string fileName = to_string(tc) + ".in"; freopen(fileName.c_str(), "w", stdout); tc++; int S = 300000; tests.clear(); genGood(S / 2, 1, 100); genBad(S / 2, 1, 100); cout << tests.size() << endl; for (auto s: tests) { cout << s << endl; } } void addTests4() { string fileName = to_string(tc) + ".in"; freopen(fileName.c_str(), "w", stdout); tc++; int S = 300000; tests.clear(); genGood(S / 2, 5000, 10000); genBad(S / 2, 5000, 10000); cout << tests.size() << endl; for (auto s: tests) { cout << s << endl; } } void addTests5() { string fileName = to_string(tc) + ".in"; freopen(fileName.c_str(), "w", stdout); tc++; int S = 200000; tests.clear(); genGood(S, 49999, 50000); genBad(S / 2, 49999, 50000); cout << tests.size() << endl; for (auto s: tests) { cout << s << endl; } } int bruteForce(string s) { vector indices; for (int i = 0; i < s.size(); i++) { if (s[i] != '.') { indices.push_back(i); } } vector leftRange(s.size()), rightRange(s.size()); for (int i = 0; i < s.size(); i++) { if (s[i] != '.') { leftRange[i] = min(s[i] - '0', i); rightRange[i] = min(s[i] - '0', (int) s.size() - i - 1); } } int n = s.size(); for (int mask = 0; mask < (1 << indices.size()); mask++) { vector dirs(n, -1); for (int i = 0; i < indices.size(); i++) { if (mask & (1 << i)) { dirs[indices[i]] = 1; } } int ok = true; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n && j - i < 20; j++) { if (s[i] != '.' && s[j] != '.') { int l1 = leftRange[i]; int r1 = rightRange[i]; int l2 = leftRange[j]; int r2 = rightRange[j]; int d1 = dirs[i] == -1 ? 0 : 1; int d2 = dirs[j] == -1 ? 0 : 1; if (can_robots_meet[l1][r1][l2][r2][d1][d2][j - i]) { ok = false; break; } } } } if (ok) { return true; } } return false; } int check_everything(string s) { NUM_VERTICES = 2 * s.size(); init(); vector leftRange(s.size()), rightRange(s.size()); for (int i = 0; i < s.size(); i++) { if (s[i] != '.') { leftRange[i] = min(s[i] - '0', i); rightRange[i] = min(s[i] - '0', (int) s.size() - i - 1); } } // tr(leftRange); // tr(rightRange); for (int i = 0; i < s.size(); i++) { for (int j = i; j < i + 20 && j < s.size(); j++) { if (s[i] != '.' && s[j] != '.') { for (int dir1 = -1; dir1 <= 1; dir1++) if (dir1 != 0) { for (int dir2 = -1; dir2 <= 1; dir2++) if (dir2 != 0) { int l1 = leftRange[i]; int r1 = rightRange[i]; int l2 = leftRange[j]; int r2 = rightRange[j]; int d1 = dir1 == -1 ? 0 : 1; int d2 = dir2 == -1 ? 0 : 1; if (can_robots_meet[l1][r1][l2][r2][d1][d2][j - i]) { // tr(i, j, l1, r1, l2, r2, d1, d2, j - i, s[i], s[j]); // addXor(2 * i + d1, 2 * j + d2); addImplication(2 * i + d1, 2 * j + (d2 ^ 1)); } } } } } } bool ok = solve(); cout << (ok ? "safe" : "unsafe") << endl; //int bok = bruteForce(s); //cout << (bok ? "safe" : "unsafe") << endl; //cerr << endl; //assert(ok == bok); return ok; } vector brute_data; void recursion(string s) { if (s.size() > 7) { return; } if (s.size() >= 1) { brute_data.push_back(s); } recursion(s + "."); for (char ch = '0'; ch <= '6'; ch++) { string t = s; t += ch; recursion(t); } } void genTests() { addTests1(); addTests2(); addTests3(); addTests4(); addTests5(); } void bruteforce_it() { recursion(""); cerr << brute_data.size() << endl; int cnt = 0; int processed = 0; for (string s: brute_data) { processed++; cerr << "processed " << processed << endl; int ok = check_everything(s); cnt += ok; } cerr << "safe cnt " << cnt << endl; } void solveProblem() { int T; cin >> T; while (T--) { string s; cin >> s; check_everything(s); } } int main() { precompute(); //genTests(); solveProblem(); // Robot a(2, 2); // Robot b(2, 2); // int ok = canMeet(a, b, 1, 1, 2); // printf("ok = %d\n", ok); return 0; }