QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#257983#1965. Triodel17WA 1ms3504kbC++148.6kb2023-11-19 14:10:062023-11-19 14:10:08

Judging History

你现在查看的是最新测评结果

  • [2023-11-19 14:10:08]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3504kb
查看
  • [2023-11-19 14:10:06]
  • 提交

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;
}
Source code, Language: C++14

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'
English 繁體中文 简体中文

Server Time: 2024-11-29 20:51:17 | OpenSource Project