QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #296770 | #4826. Find the Parts | defyers# | 0 | 1ms | 3620kb | C++17 | 6.2kb | 2024-01-03 16:05:40 | 2024-01-03 16:05:40 |
answer
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using LL = long long;
int r, c;
string s;
int a[2005][2005];
vector<int> ans;
int h[2005][2005];
pair<int, int> p[2005][2005];
int qa[55][55];
unordered_map<LL, pair<int, int>> M;
int sw(char c) {
if (c >= '0' && c <= '9') {
return c - '0';
}
return c - 'A' + 10;
}
int H(int r1, int c1, int r2, int c2) {
int num = qa[r1][c1] ^ qa[r1 - 1][c1] ^ qa[r1][c1 - 1] ^ qa[r1 - 1][c1 - 1];
//cout << "at H " << num << (qa[r2][c2] ^ qa[r1 - 1][c2] ^ qa[r2][c1 - 1] ^ qa[r1 - 1][c1 - 1]) << endl;
return (num + (qa[r2][c2] ^ qa[r1 - 1][c2] ^ qa[r2][c1 - 1] ^ qa[r1 - 1][c1 - 1])) % 256;
}
int tonum(string s) {
int a0 = sw(s[0]);
int a1 = sw(s[1]);
return a0 * 16 + a1;
}
string st(int x) {
string s;
if (x > 9) s += (x - 10 + 'A');
else s += (x + '0');
return s;
}
string tostring(int num) {
int a0 = num / 16;
int a1 = num % 16;
return st(a0) + st(a1);
}
void encode() {
//cout << tostring(255) << endl;
cin >> r >> c;
ans.push_back(r / 256);
ans.push_back(r % 256);
ans.push_back(c / 256);
ans.push_back(c % 256);
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
cin >> s;
int num = tonum(s);
a[i][j] = num;
}
}
int ilen = 3;
for (int i = 1; i + ilen - 1 <= r; ) {
int jlen = 3;
for (int j = 1; j + jlen - 1 <= c; ) {
int x = 0;
for (int ii = i; ii < i + ilen; ii++) {
for (int jj = j; jj < j + jlen; jj++) {
x ^= a[ii][jj];
}
}
//cout << "(" << x << "+"<< a[i][j] << ") ";
x = (x + a[i][j]) % 256;
ans.push_back(x);
j += jlen;
jlen = 7 - jlen;
}
//cout << endl;
i += ilen;
ilen = 7 - ilen;
}
cout << (int)ans.size() << "\n";
for (int i = 0; i < ans.size(); i++) {
cout << tostring(ans[i]);
cout << " \n"[i == ans.size() - 1];
}
}
void decode() {
int n;
cin >> n;
string s1, s2, s3, s4;
cin >> s1 >> s2 >> s3 >> s4;
int a1 = tonum(s1), a2 = tonum(s2), a3 = tonum(s3), a4 = tonum(s4);
r = a1 * 256 + a2;
c = a3 * 256 + a4;
//cout << "r and c : " << r << " " << c << endl;
int i = 1, j = 1, ilen = 3, jlen = 3;
int hi = 1, hj = 1;
for (int t = 5; t <= n; t++) {
string s;
cin >> s;
if (j + jlen - 1 > c) {
i += ilen;
j = 1;
hi++;
hj = 1;
ilen = 7 - ilen;
jlen = 3;
}
h[hi][hj] = tonum(s);
p[hi][hj] = {i, j};
hj++;
j += jlen;
jlen = 7 - jlen;
}
//cout << "hashed array size: " << hi << " " << hj << endl;
for (int i = 1; i < hi; i++) {
for (int j = 1; j < hj; j++) {
ll num = h[i][j];
num = num * 256 + h[i][j + 1];
num = num * 256 + h[i + 1][j];
num = num * 256 + h[i + 1][j + 1];
M[num] = p[i][j];
}
}
int q;
cin >> q;
for (int qi = 1; qi <= q; qi++) {
int qr, qc;
cin >> qr >> qc;
for (int j = 1; j <= qr; j++) {
for (int k = 1; k <= qc; k++) {
string tmp;
cin >> tmp;
int num = tonum(tmp);
qa[j][k] = num;
}
}
for (int i = 1; i <= qr; i++) {
for (int j = 1; j <= qc; j++) {
qa[i][j] = qa[i][j] ^ qa[i][j - 1] ^ qa[i - 1][j] ^ qa[i - 1][j - 1];
}
}
pair<int, int> position = {-1, -1};
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
LL num = H(i, j, i + 2, j + 2);
num = num * 256 + H(i, j + 3, i + 2, j + 6);
num = num * 256 + H(i + 3, j, i + 6, j + 2);
num = num * 256 + H(i + 3, j + 3, i + 6, j + 6);
if (M.find(num) != M.end()) {
if (position == M[num]) continue;
if (position.first != -1) while (true) {}
auto pr = M[num];
position.first = pr.first - i + 1;
position.second = pr.second - j + 1;
}
}
}
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
LL num = H(i, j, i + 2, j + 3);
num = num * 256 + H(i, j + 4, i + 2, j + 6);
num = num * 256 + H(i + 3, j, i + 6, j + 3);
num = num * 256 + H(i + 3, j + 4, i + 6, j + 6);
if (0 && i == 1 && j == 3) {
cout << "to get " << H(i, j, i + 2, j + 3) << ", from:\n";
int tmp = 0;
for (int ii = i; ii <= i + 2; ii++) {
for (int jj = j; jj <= j + 3; jj++) {
cout << (qa[ii][jj] ^ qa[ii - 1][jj] ^ qa[ii][jj - 1] ^ qa[ii - 1][jj - 1]) << " ";
tmp ^= (qa[ii][jj] ^ qa[ii - 1][jj] ^ qa[ii][jj - 1] ^ qa[ii - 1][jj - 1]);
}
cout << (qa[i][j] ^ qa[i - 1][j] ^ qa[i][j - 1] ^ qa[i - 1][j - 1]) << "+" << tmp << endl;
cout << endl;
}
cout << H(i, j, i + 2, j + 3) << " ";
cout << H(i, j + 4, i + 2, j + 6) << endl;
cout << H(i + 3, j, i + 6, j + 3) << " ";
cout << H(i + 3, j + 4, i + 6, j + 6) << endl;
}
if (M.find(num) != M.end()) {
if (position == M[num]) continue;
if (position.first != -1) while (true) {}
auto pr = M[num];
position.first = pr.first - i + 1;
position.second = pr.second - j + 1;
}
}
}
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
LL num = H(i, j, i + 3, j + 2);
num = num * 256 + H(i, j + 3, i + 3, j + 6);
num = num * 256 + H(i + 4, j, i + 6, j + 2);
num = num * 256 + H(i + 4, j + 3, i + 6, j + 6);
if (M.find(num) != M.end()) {
if (position == M[num]) continue;
if (position.first != -1) while (true) {}
auto pr = M[num];
position.first = pr.first - i + 1;
position.second = pr.second - j + 1;
}
}
}
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
LL num = H(i, j, i + 3, j + 3);
num = num * 256 + H(i, j + 4, i + 3, j + 6);
num = num * 256 + H(i + 4, j, i + 6, j + 3);
num = num * 256 + H(i + 4, j + 3, i + 6, j + 6);
if (M.find(num) != M.end()) {
if (position == M[num]) continue;
if (position.first != -1) while (true) {}
auto pr = M[num];
position.first = pr.first - i + 1;
position.second = pr.second - j + 1;
}
}
}
assert(position.first != -1);
cout << position.first << " " << position.second << "\n";
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cout << fixed << setprecision(10);
string s;
cin >> s;
if (s[0] == 'm') {
encode();
}
else {
decode();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3600kb
input:
message 20 24 33 39 73 4A 5A AA E0 86 96 4B 0B 83 A0 FA 82 9B B0 6E DC 03 1C B9 5B 81 86 3E 23 7B C9 38 77 82 7D 62 EA CE A8 DE 85 6C 36 B3 10 EE 85 6A D5 92 14 BD 58 74 20 7B 36 E1 89 B8 6F 4A F4 8F 17 2E 2F 0F 79 DD AA 9F 6F AD 85 21 B6 2F 58 37 87 7B 3F EE D9 7D 9A E6 AA 12 E0 B6 BB 3D 72 BD 34 A...
output:
39 00 14 00 18 46 08 9C E9 E2 D2 CC 91 4E 08 15 EB B7 E6 91 3E CD 61 6F C9 E1 3E CB FF 5B 8E 9D C0 60 12 66 0C 16 F9 BC
input:
parts 39 00 14 00 18 46 08 9C E9 E2 D2 CC 91 4E 08 15 EB B7 E6 91 3E CD 61 6F C9 E1 3E CB FF 5B 8E 9D C0 60 12 66 0C 16 F9 BC 2 10 10 39 73 4A 5A AA E0 86 96 4B 0B 3E 23 7B C9 38 77 82 7D 62 EA BD 58 74 20 7B 36 E1 89 B8 6F 21 B6 2F 58 37 87 7B 3F EE D9 8A 73 EE 69 BF E0 0D 5C 57 EF F7 4F A7 18 4D 7...
output:
1 2 6 5
result:
ok correct answer
Test #2:
score: 100
Accepted
time: 1ms
memory: 3620kb
input:
message 20 20 85 C4 91 58 77 23 A9 E5 44 8E 28 DC A2 51 13 AE 4E 3C 21 62 37 5A 41 45 8F CA C3 89 01 68 11 72 D8 75 72 ED EE 64 FA B0 05 45 6E F2 FD CE 9A AC 31 CA 88 83 34 D6 23 1F 8C 6D 9E 8C 42 40 7E 18 4C D1 D3 F2 02 20 51 20 14 0F 3D 27 0E 03 73 D7 C0 1F C3 1D D3 55 D9 AF 6E 76 77 28 24 1A 97 E...
output:
29 00 14 00 14 57 95 7D 48 45 85 A4 CC 08 9B C0 AC 3A 41 AC 38 5C 8F AF CF 4F 58 B0 71 5A
input:
parts 29 00 14 00 14 57 95 7D 48 45 85 A4 CC 08 9B C0 AC 3A 41 AC 38 5C 8F AF CF 4F 58 B0 71 5A 1 10 10 D0 0A D3 6D B9 31 31 76 54 15 CE 14 02 1A A2 8C 77 EB 8E 02 06 44 E4 F4 22 DB 66 F8 7E 38 C6 6A B7 5F E1 A0 0D F0 F5 8A AC DB B0 FB 26 E6 12 36 37 F1 6C AB B1 4C C0 11 B6 DE 71 C2 09 54 23 45 56 1...
output:
6 6
result:
ok correct answer
Test #3:
score: 0
Stage 2: Program answer Time Limit Exceeded
input:
message 20 20 12 4F 58 0D 8B AB 72 D1 55 0F FC 74 28 E3 B0 02 9E FA 18 C0 82 72 32 EB 29 EF 9D 70 E6 2D AC 15 37 31 40 A4 36 B6 58 2C 4E C2 4D AC C5 0F D1 A8 B2 2D 43 ED 00 63 7C 3B 3E C5 94 49 92 7D 2C 69 2B 6A 15 95 7C FD 67 E4 AC EE 01 F8 78 5F 46 57 54 7D 03 92 36 85 D0 C0 B1 14 22 70 9D 06 4E C...
output:
29 00 14 00 14 18 65 D8 2D 37 38 37 A6 A1 4A 84 9B C4 4A 38 E3 B8 65 97 7D 45 69 A8 F8 A7
input:
parts 29 00 14 00 14 18 65 D8 2D 37 38 37 A6 A1 4A 84 9B C4 4A 38 E3 B8 65 97 7D 45 69 A8 F8 A7 9 10 10 12 4F 58 0D 8B AB 72 D1 55 0F 82 72 32 EB 29 EF 9D 70 E6 2D 4E C2 4D AC C5 0F D1 A8 B2 2D 92 7D 2C 69 2B 6A 15 95 7C FD 54 7D 03 92 36 85 D0 C0 B1 14 A7 42 36 1E F1 E2 B4 20 D7 FE 8D 5E 4F 0C 4E B...