QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#257983 | #1965. Trio | del17 | WA | 1ms | 3504kb | C++14 | 8.6kb | 2023-11-19 14:10:06 | 2023-11-19 14:10:08 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <unordered_set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define plii pair<ll,pair<int,int>>
#define heapmax(type) priority_queue<type>
#define heapmin(type) priority_queue<type,vector<type>,greater<type>>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define FASTIO ios::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
#define getbit(mask,i) ((mask >> i) & 1)
template<typename T> bool maximize(const T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(const T &res, const T &val) { if (res > val) { res = val; return true; } return false; }
template<typename T> ll rv_num(T x){
ll res = 0;
while (x > 0) res = res*10 + x % 10 , x/=10;
return res;
}
const ll mod = 1e9 + 7;
const ld PI = acos(-1);
const int N = 2e5 + 100;
const int N_Trie = 1e5;
const int N_ST = 2e5 + 10;
const int N_BIT = 2e5 + 10;
const int ooint = (1LL << 31) - 1;
// const ll ooll = (1LL << 63) - 1;
const int LIM = 1e7; // N_Prime
const int N_MST = 1e5; // N of Merge Sort Tree
const int N_Hash = 2e6 + 10;
ll power(ll a,ll b,ll c){ // O(log(b))
ll res = 1;
a = a % c;
for (; b > 0; b >>= 1 , a = a * a % c)
if (b & 1) res = res * a % c;
return res;
}
int n , dp[10][10][10][10];
int pre[10][10][10][10] , gg[10][10][10][10];
int p[5], r[5];
int a[N][5];
void up(int i){
dp[a[i][1]][a[i][2]][a[i][3]][a[i][4]]++;
}
void down(int i){
dp[a[i][1]][a[i][2]][a[i][3]][a[i][4]]--;
}
ll res = 0;
// void bactr(int x, int d){
// if (p[x] != 0){
// for (int i = 1; i <= 9; i++){
// if (i == p[x]) continue;
// r[x] = i;
// if (x < 4) bactr(x + 1,d);
// if (x == 4){
// if (d % 2 == 1) res = res + gg[r[1]][r[2]][r[3]][r[4]];
// else res = res - gg[r[1]][r[2]][r[3]][r[4]];
// }
// }
// } else {
// r[x] = 0;
// if (x < 4) bactr(x + 1,d);
// if (x == 4){
// if (d % 2 == 1) res = res + gg[r[1]][r[2]][r[3]][r[4]];
// else res = res - gg[r[1]][r[2]][r[3]][r[4]];
// }
// }
// }
void up_z(int x){
for (int mask = 0; mask < (1 << 4); mask++){
for (int c = 0; c < 4; c++){
if (((mask >> c) & 1))
p[c + 1] = a[x][c + 1];
else
p[c + 1] = 0;
}
gg[p[1]][p[2]][p[3]][p[4]]++;
}
}
void down_z(int x){
for (int mask = 0; mask < (1 << 4); mask++){
for (int c = 0; c < 4; c++){
if (((mask >> c) & 1))
p[c + 1] = a[x][c + 1];
else
p[c + 1] = 0;
}
gg[p[1]][p[2]][p[3]][p[4]]--;
}
}
int ep[5][3], w[5];
void backtrack(int x, int d){
if (r[x] == 1){
w[x] = p[x];
if (x < 4) backtrack(x + 1,d);
if (x == 4){
//if (d + (w[x] != 0) == 0) return;
if ((d + (w[x] != 0)) % 2 == 1)
res = res - gg[w[1]][w[2]][w[3]][w[4]];
else
res = res + gg[w[1]][w[2]][w[3]][w[4]];
//for (int c = 1; c <= 4; c++) cout << w[c] << " "; cout << "\n";
}
} else {
for (int k = 1; k <= 3; k++){
w[x] = ep[x][k];
if (x < 4) backtrack(x + 1,d + (w[x] != 0));
if (x == 4){
//if (d + (w[x] != 0) == 0) return;
if ((d + (w[x] != 0)) % 2 == 1)
res = res - gg[w[1]][w[2]][w[3]][w[4]];
else
res = res + gg[w[1]][w[2]][w[3]][w[4]];
//for (int c = 1; c <= 4; c++) cout << w[c] << " "; cout << "\n";
}
}
}
}
int main()
{
FASTIO;
cin >> n;
for (int i = 1; i <= n; i++){
string s; cin >> s;
for (int j = 0; j < s.size(); j++)
a[i][j + 1] = s[j] - 48;
}
// for (int i = 1; i <= n; i++){
// up(i);
// }
// for (int i1 = 1; i1 < 10; i1++){
// for (int i2 = 1; i2 < 10; i2++){
// for (int i3 = 1; i3 < 10; i3++){
// for (int i4 = 1; i4 < 10; i4++){
// pre[i1][i2][i3][i4] = pre[i1][i2][i3][i4 - 1] + dp[i1][i2][i3][i4];
// }
// pre[i1][i2][i3][0] = pre[i1][i2][i3][9];
// pre[i1][i2][i3][0] = pre[i1][i2][i3 - 1][0] + pre[i1][i2][i3][0];
// }
// pre[i1][i2][0][0] = pre[i1][i2][9][0];
// pre[i1][i2][0][0] = pre[i1][i2 - 1][0][0] + pre[i1][i2][0][0];
// }
// pre[i1][0][0][0] = pre[i1][9][0][0];;
// pre[i1][0][0][0] = pre[i1 - 1][0][0][0] + pre[i1][0][0][0];
// }
// pre[0][0][0][0] = pre[9][0][0][0];
// ll res = 0;
// bool rt[5];
// for (int i = 1; i <= n; i++){
// for (int j = 1; j <= n; j++){
// if (i == j) continue;
// for (int mask = 1; mask < (1 << 4); mask++){
// bool cc = true;
// for (int c = 0; c < 4; c++){
// if ((mask >> c) & 1){
// if (a[i][c + 1] == a[j][c + 1]){
// p[c + 1] = a[i][c + 1];
// } else {
// cc = false;
// break;
// }
// } else {
// p[c + 1] = 0;
// }
// }
// if (cc){
// gg[p[1]][p[2]][p[3]][p[4]]++;
// }
// }
// }
// }
// // cout << "dcm : " << gg[0][0][4][0] << "\n";
// for (int i = 1; i <= n; i++){
// for (int j = 1; j <= n; j++){
// if (i == j) continue;
// for (int mask = 1; mask < (1 << 4); mask++){
// bool cc = true;
// for (int c = 0; c < 4; c++){
// if ((mask >> c) & 1){
// if (a[i][c + 1] == a[j][c + 1]){
// p[c + 1] = a[i][c + 1];
// } else {
// cc = false;
// break;
// }
// } else {
// p[c + 1] = 0;
// }
// }
// if (cc){
// gg[p[1]][p[2]][p[3]][p[4]]--;
// }
// }
// }
// for (int mask = 1; mask < (1 << 4); mask++){
// int d = 0;
// for (int c = 0; c < 4; c++){
// if ((mask >> c) & 1)
// p[c + 1] = a[i][c + 1] , d++;
// else
// p[c + 1] = 0;
// }
// bactr(1,d);
// }
// cout << res << "\n";
// }
for (int i = 1; i <= n; i++) up_z(i);
//cout << "zzz : " << gg[1][0][0][3] << "\n";
//cout << gg[0][0][0][0] << "\n";
for (int i = 1; i <= n; i++){
down_z(i);
for (int j = i + 1; j <= n; j++){
down_z(j);
for (int c = 1; c <= 4; c++){
if (a[i][c] == a[j][c]) r[c] = 1;
else r[c] = 0;
}
for (int c = 1; c <= 4; c++){
if (r[c] == 1) p[c] = a[i][c];
else{
p[c] = 0;
ep[c][1] = 0;
ep[c][2] = a[i][c];
ep[c][3] = a[j][c];
}
}
//res = res + gg[p[1]][p[2]][p[3]][p[4]];
backtrack(1,0);
// cout << res << "\n";
}
for (int j = i + 1; j <= n; j++) up_z(j);
}
cout << abs(res); //- (n*(n-1)*(n-2)/6);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3396kb
input:
4 1234 2345 3456 4567
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3440kb
input:
9 1299 2399 3499 4599 5699 6799 7899 8999 9199
output:
84
result:
ok single line: '84'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
9 1239 2349 3459 4569 5679 6789 7899 8919 9129
output:
84
result:
ok single line: '84'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3468kb
input:
9 1999 2999 3999 4999 5999 6999 7999 8999 9999
output:
84
result:
ok single line: '84'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3412kb
input:
9 1234 2345 3456 4567 5678 6789 7891 8912 9123
output:
84
result:
ok single line: '84'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3448kb
input:
18 1211 2311 3411 4511 5611 6711 7811 8911 9111 1222 2322 3422 4522 5622 6722 7822 8922 9122
output:
168
result:
ok single line: '168'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3448kb
input:
17 1211 2311 3411 4511 5611 6711 7811 8911 9111 1231 2341 3451 4561 5671 6781 7891 9121
output:
336
result:
ok single line: '336'
Test #8:
score: -100
Wrong Answer
time: 1ms
memory: 3504kb
input:
81 1211 2311 3411 4511 5611 6711 7811 8911 9111 1222 2322 3422 4522 5622 6722 7822 8922 9122 1233 2333 3433 4533 5633 6733 7833 8933 9133 1244 2344 3444 4544 5644 6744 7844 8944 9144 1255 2355 3455 4555 5655 6755 7855 8955 9155 1266 2366 3466 4566 5666 6766 7866 8966 9166 1277 2377 3477 4577 5677 67...
output:
42336
result:
wrong answer 1st lines differ - expected: '43848', found: '42336'