QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#791148 | #5254. Differences | jhinezeal123 | TL | 0ms | 0kb | C++20 | 1.8kb | 2024-11-28 17:07:28 | 2024-11-28 17:07:29 |
answer
#include <bits/stdc++.h>
// #define int long long
#define ii pair<int, int>
#define iii pair<int,ii>
#define vii vector<ii>
#define fi first
#define se second
#define endl '\n'
#define show(T) {for (auto x:T) cout<<x<<' ';cout<<endl;}
#define all(T) T.begin(),T.end()
#pragma GCC O("fast")
using namespace std;
const double eps = 0.0001;
const int mod =/*998244353*/ 1e9+7;
const int N = 1005;
const int MATRIX_SIZE = 64;
const int BLOCK=500;
const long long oo=1e18;
int n,m,k,num[100005][6];
vector <vector<char>> T;
vector <int> vitri,matuy;
char c;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l,int r){
return uniform_int_distribution<int>(l,r)(rd);
}
int get(int a,int b){
int res=0;
for (int i=1;i<=m;++i)
res+=(T[a][i]!=T[b][i]);
return res;
}
bool check(int pos){
random_shuffle(all(vitri));
for (auto x:vitri){
if (x==pos) continue;
if (get(pos,x)!=k) return false;
}
return true;
}
void solve(){
cin>>n>>m>>k;
for (int i=1;i<=n;++i) {
vitri.push_back(i);
matuy.push_back(i);
}
T.resize(n+5,vector<char>(m+5));
for (int i=1;i<=n;++i){
for (int j=1;j<=m;++j){
// cout<<i<<' '<<j<<endl;
cin>>c;
++num[j][c-'A'];
T[i][j]=c;
}
}
random_shuffle(all(matuy));
for (int p=0,i;p<n;++p){
i=matuy[p];
int sum=0;
for (int j=1;j<=m;++j)
sum+=num[j][T[i][j]-'A']-1;
// cout<<i<<' '<<sum<<endl;
if (sum!=(m-k)*(n-1)) continue;
if (check(i)) return void(cout<<i);
}
}
main() {
//freopen("ok.inp","r",stdin);
//freopen("kiemtra.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
// cout<<endl<<clock()/1000.0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
3585 4096 2048 ABBBBBBAABAAAAAAAAAAAAABAABABBBABABAAAAABABAAAABAABAABBABBAABAABABBABAABBABBABABABBAAAABBABAABBBBABBBAABBBBBABAABAAABAAABBBBAAAABAABAABABABABBBBBABAAABAAABBAABABBABAABBAABBAABABBBBAABAAAABAABBABAAABBAAAAAABAABBABBABAABABBBAABABBABABBBAAAAABBBABABABBAABAAAABBBBABABAABBBABABABBAABBBABAB...