QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#458408 | #8830. Breaking Bad | ucup-team112# | WA | 885ms | 11776kb | C++23 | 3.9kb | 2024-06-29 17:08:46 | 2024-06-29 17:08:47 |
Judging History
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'