QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#458408#8830. Breaking Baducup-team112#WA 885ms11776kbC++233.9kb2024-06-29 17:08:462024-06-29 17:08:47

Judging History

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

  • [2024-06-29 17:08:47]
  • 评测
  • 测评结果:WA
  • 用时:885ms
  • 内存:11776kb
  • [2024-06-29 17:08:46]
  • 提交

answer


#include <bits/stdc++.h>
#include <iostream>
#include <limits>
#include <numeric>
#include <type_traits>
#include <bitset>
#include <map>
#include <unordered_map>
#include <set>
#include <random>

using namespace std;
using ll = long long;

#define rep(i,n,m) for(ll (i)=(n);(i)<(m);(i)++)
#define rrep(i,n,m) for(ll (i)=(n);(i)>(m);(i)--)
const ll mod = 998244353;
const ll inf = 1e18;
const ll INF = 4e18+10;

using pll = pair<ll,ll>;

void pline(vector<int> lis){
    rep(i,0,lis.size()){
        printf ("%d",lis[i]);
        if (i != lis.size()-1) printf(" ");
        else printf("\n");
    }
}

void pline(vector<ll> lis){
    rep(i,0,lis.size()){
        printf ("%lld",lis[i]);
        if (i != lis.size()-1) printf(" ");
        else printf("\n");
    }
}

void pline2(vector<ll> lis){
    rep(i,0,lis.size()){
        printf ("%lld",lis[i]);
        if (i != lis.size()-1) printf("");
        else printf("\n");
    }
}

void pline(vector<pair<ll,ll>> lis){
    rep(i,0,lis.size()){
        printf ("/%lld,%lld/",lis[i].first,lis[i].second);
        if (i != lis.size()-1) printf(" ");
        else printf("\n");
    }
}

int main() {

    clock_t start = clock();

    ll n;
    cin >> n;
    
    vector<vector<ll>> a(n, vector<ll> (n));
    rep(i,0,n){
        rep(j,0,n){
            cin >> a[i][j];
        }
    }

    vector<ll> exist_col;
    vector<ll> exist_row;
    vector<ll> same_col;
    vector<ll> same_row;

    rep(i,0,n){
        bool flag = true;
        rep(j,0,n-1){
            if (a[i][j] != a[i][j+1]){
                flag = false;
            }
        }
        if (flag){
            same_row.push_back(i);
        }else{
            exist_row.push_back(i);
        }
    }

    rep(j,0,n){
        bool flag = true;
        rep(i,0,n-1){
            if (a[i][j] != a[i+1][j]){
                flag = false;
            }
        }
        if (flag){
            same_col.push_back(j);
        }else{
            exist_col.push_back(j);
        }
    }

    //pline(same_row);
    //pline(same_col);
    std::random_device seed_gen;
    std::mt19937 engine(seed_gen());

    vector<bool> ans(5,false); 
    if ( same_row.size() * same_col.size() == 0 ){
        
        ll base = 0;
        for (auto i : same_row){
            base += a[i][0];
        }
        for (auto j : same_col){
            base += a[0][j];
        }

        while(true){
            std::shuffle(exist_row.begin(), exist_row.end(), engine);
            std::shuffle(exist_col.begin(), exist_col.end(), engine);
            ll now = base;
            rep(x, 0, min(exist_col.size(),exist_row.size()) ){
                now += a[ exist_row[x] ][ exist_col[x] ];
            }
            ans[now % 5] = true;

            double time = static_cast<double>(clock() - start) / CLOCKS_PER_SEC * 1000.0;
            if (time >= 900) break;
        }

    }else{

        ll base_one = a[ same_row[0] ][ same_col[0] ];
        ll h = exist_row.size();
        ll w = exist_col.size();
        ll select_min = n - min(n , (n-h) + (n-w));
        ll select_max = min(h,w);
        std::uniform_int_distribution<> distr(select_min, select_max);

        while(true){
            std::shuffle(exist_row.begin(), exist_row.end(), engine);
            std::shuffle(exist_col.begin(), exist_col.end(), engine);
            ll select_k = distr(engine);

            ll now = base_one * (n-select_k);
            rep(x, 0, select_k){
                now += a[ exist_row[x] ][ exist_col[x] ];
            }
            ans[now % 5] = true;

            double time = static_cast<double>(clock() - start) / CLOCKS_PER_SEC * 1000.0;
            if (time >= 900) break;
        }

    }

    rep(i,0,5){
        if (ans[i]) cout << "Y";
        else cout << "N";
    }
    cout << endl;

}

/*

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 367ms
memory: 3632kb

input:

2
0 4
4 0

output:

YNNYN

result:

ok "YNNYN"

Test #2:

score: 0
Accepted
time: 338ms
memory: 3696kb

input:

2
1 1
1 1

output:

NNYNN

result:

ok "NNYNN"

Test #3:

score: 0
Accepted
time: 518ms
memory: 3676kb

input:

4
0 0 1 0
0 1 0 1
0 0 0 0
1 1 0 0

output:

YYYYN

result:

ok "YYYYN"

Test #4:

score: 0
Accepted
time: 450ms
memory: 3900kb

input:

4
0 0 0 1
0 1 0 1
1 0 0 0
0 1 0 0

output:

YYYYN

result:

ok "YYYYN"

Test #5:

score: 0
Accepted
time: 517ms
memory: 3740kb

input:

10
1 4 2 0 0 2 0 1 3 3
0 3 1 4 4 1 4 0 2 2
1 4 2 0 0 2 0 1 0 3
0 3 1 4 4 1 4 0 2 2
4 2 0 3 3 0 3 4 1 1
2 0 3 1 1 3 1 2 4 4
4 2 0 3 3 0 3 4 1 1
2 0 3 1 1 3 1 2 4 4
1 4 2 0 0 2 0 1 3 3
3 1 4 2 2 4 2 3 0 0

output:

NYNNY

result:

ok "NYNNY"

Test #6:

score: 0
Accepted
time: 554ms
memory: 3768kb

input:

10
4 4 4 1 3 4 1 4 3 0
3 3 3 0 2 3 0 3 2 4
3 3 3 0 2 3 0 3 2 4
4 4 4 1 3 4 1 4 3 0
2 2 2 4 1 2 4 2 1 3
2 2 2 4 1 3 4 2 1 3
4 4 4 1 3 4 1 4 3 0
3 3 3 0 2 3 0 3 2 4
2 2 2 4 1 2 4 2 1 3
4 4 4 1 3 4 1 1 3 0

output:

YYYNY

result:

ok "YYYNY"

Test #7:

score: 0
Accepted
time: 557ms
memory: 3672kb

input:

10
1 2 0 4 2 3 4 0 2 3
0 1 4 3 1 2 3 4 1 2
4 0 3 2 0 1 2 3 0 1
1 2 0 4 2 3 4 0 2 3
3 4 2 1 4 0 1 2 4 0
0 1 4 3 1 2 3 4 1 2
2 3 1 0 3 4 0 1 3 4
3 1 1 1 4 0 1 2 4 0
1 2 0 4 2 3 4 0 2 3
1 3 0 4 2 3 4 0 2 3

output:

NYYYY

result:

ok "NYYYY"

Test #8:

score: 0
Accepted
time: 514ms
memory: 3644kb

input:

10
3 4 0 3 2 2 0 4 0 2
0 1 2 0 4 4 2 1 2 4
2 3 4 2 1 1 4 3 4 1
0 1 2 0 4 4 2 1 2 4
0 1 2 0 4 4 2 1 2 4
0 1 2 0 4 4 2 1 2 4
3 4 0 3 2 2 0 4 0 2
0 1 2 0 4 4 2 1 2 4
3 4 0 3 2 2 0 4 0 2
0 1 2 0 4 4 2 1 2 4

output:

NYNNN

result:

ok "NYNNN"

Test #9:

score: 0
Accepted
time: 550ms
memory: 3700kb

input:

10
4 1 3 1 2 0 3 2 4 4
0 2 4 2 3 1 4 3 0 0
1 1 1 1 2 0 3 2 4 1
2 4 1 4 0 3 1 0 2 2
1 3 0 3 4 2 0 4 1 1
2 4 1 4 0 3 1 0 2 2
2 4 1 4 0 3 1 0 2 2
0 2 4 2 3 1 4 3 0 0
3 0 2 1 1 4 2 1 3 3
4 1 3 1 2 0 3 2 4 4

output:

YYYYY

result:

ok "YYYYY"

Test #10:

score: 0
Accepted
time: 545ms
memory: 3700kb

input:

10
1 2 0 2 4 2 3 1 2 1
4 0 3 0 2 0 1 4 0 4
0 1 4 1 3 1 2 0 1 0
0 1 4 1 3 1 2 0 1 0
3 4 2 4 1 4 0 3 4 3
4 0 3 0 2 0 1 4 0 4
0 1 4 1 3 1 2 0 1 0
0 1 4 1 3 1 2 0 1 0
3 4 2 4 1 4 0 3 4 3
0 1 4 1 3 1 2 0 1 0

output:

NNNYN

result:

ok "NNNYN"

Test #11:

score: 0
Accepted
time: 518ms
memory: 3696kb

input:

10
1 4 1 2 1 3 3 2 1 2
0 3 0 1 0 2 2 1 0 1
0 4 0 3 0 2 2 1 0 1
1 4 1 2 1 3 3 2 1 2
4 2 4 0 4 1 1 0 4 0
1 1 1 4 1 0 3 2 1 2
0 0 0 1 0 2 2 1 0 1
2 0 2 3 2 4 4 3 2 3
2 0 2 3 2 4 4 3 2 3
2 0 2 3 2 4 4 3 2 3

output:

YYYYY

result:

ok "YYYYY"

Test #12:

score: 0
Accepted
time: 550ms
memory: 3700kb

input:

10
1 2 0 1 4 0 1 2 2 2
1 2 0 1 4 3 1 2 2 2
0 1 4 0 3 1 0 1 1 1
1 2 0 1 4 3 1 2 2 2
3 4 2 3 1 4 3 4 4 4
0 1 4 0 3 1 0 1 1 1
4 0 3 4 2 0 4 0 0 0
3 4 2 3 1 4 3 4 4 4
4 0 3 4 2 0 4 0 0 0
0 1 4 0 3 1 0 1 1 1

output:

YNYNY

result:

ok "YNYNY"

Test #13:

score: 0
Accepted
time: 560ms
memory: 3772kb

input:

10
1 3 0 0 2 1 3 4 3 3
3 3 0 0 4 1 3 4 3 3
1 1 3 3 2 4 1 2 1 1
2 4 1 1 3 2 4 0 4 4
4 1 3 3 0 4 1 2 1 1
2 4 1 1 3 2 4 0 4 4
0 2 4 4 1 0 2 3 2 2
3 0 2 2 4 3 0 1 0 0
3 0 2 2 4 3 0 1 0 0
4 2 4 4 1 0 2 3 2 2

output:

YYYNY

result:

ok "YYYNY"

Test #14:

score: 0
Accepted
time: 510ms
memory: 3936kb

input:

10
2 0 3 1 3 0 0 0 4 1
1 4 2 0 2 4 4 4 3 0
2 0 3 1 3 0 0 0 4 1
1 4 2 0 2 4 4 4 3 0
1 4 2 0 2 4 4 4 3 0
3 3 4 2 4 1 1 1 0 2
3 1 4 2 4 1 1 1 0 2
4 2 0 3 0 2 2 2 1 3
3 1 4 2 4 1 1 1 0 2
1 4 2 0 2 4 4 4 3 0

output:

YNYNN

result:

ok "YNYNN"

Test #15:

score: 0
Accepted
time: 885ms
memory: 11576kb

input:

1000
3 4 1 2 4 1 0 3 0 4 1 4 3 1 4 4 1 0 1 2 3 1 0 1 3 4 4 0 3 0 3 2 2 1 0 4 1 3 3 0 3 1 3 2 2 0 3 3 2 2 3 0 4 2 1 2 1 2 1 4 2 4 1 4 2 4 3 2 0 3 0 4 2 1 2 3 3 0 2 0 3 3 1 1 0 3 4 3 2 0 4 0 3 4 4 2 3 4 2 3 4 2 1 3 2 2 4 1 0 2 2 4 0 1 2 0 4 1 3 2 3 2 2 2 1 4 4 4 2 0 0 4 4 1 3 4 0 2 2 3 1 1 3 2 3 2 3 0...

output:

NNNYN

result:

ok "NNNYN"

Test #16:

score: -100
Wrong Answer
time: 876ms
memory: 11776kb

input:

1000
2 3 0 1 0 0 0 1 1 4 1 4 2 3 0 3 4 2 3 2 4 2 1 1 1 1 0 0 3 3 2 0 2 2 2 4 3 0 3 3 3 0 1 3 0 2 0 1 0 0 0 3 1 4 3 1 4 0 3 4 4 1 3 3 4 0 1 4 2 3 0 1 0 0 2 3 1 4 0 0 2 1 2 3 3 4 4 3 3 2 0 0 4 3 2 3 3 2 4 0 2 2 3 0 3 2 4 1 0 2 4 2 4 1 2 1 3 0 3 3 0 1 1 0 2 3 0 2 4 1 4 3 4 1 2 2 2 4 0 1 3 3 0 0 1 3 2 4...

output:

NYNYY

result:

wrong answer 1st words differ - expected: 'NYYYY', found: 'NYNYY'