QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#791148#5254. Differencesjhinezeal123TL 0ms0kbC++201.8kb2024-11-28 17:07:282024-11-28 17:07:29

Judging History

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

  • [2024-11-28 17:07:29]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-11-28 17:07:28]
  • 提交

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...

output:


result: