이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include<queue>
#include<string.h>
#include<map>
using namespace std;
#define pb push_back
#define mp make_pair
#define tl TypeLetter
#define uc UndoCommands
#define gl GetLetter
long long n,k;
long long c=64;
string s[1010];
vector< long long>block[1010];
/// TLE, 60/90 DOBIJAM.
/// Dal su ovako i drugi rjesili? hamming distancom
/// NALETIO SAM NA NEKO RJESENJE KO MOJE, PROVJERITI SLICNOSTI I RAZLIKE
long long hamming( int a, int b )
{
long long ans=0;
for( int i=0;i<block[a].size();i++ ){
// cout << a << " " << b << " " << i << " "<< block[a][i] << " tarik " <<endl;
ans+= ( long long)(__builtin_popcountll( block[a][i]^block[b][i] ));
}
return ans;
}
int main()
{
//cout << ~3 <<endl;
cin>>n>>k;
for( int i=0;i<n;i++){
cin>>s[i];
long long curr=0;
for( int j=0;j<=s[i].size();j++ ){
if( ( j%c == 0 && j > 0 ) || j==s[i].size() ){
block[i].pb( curr );
curr=0;
if( j==s[i].size() ) break;
}
if( s[i][j]=='x' ) curr|=( 1ULL<<(j%c) );
}
}
long long res=100000000;
for( int i=0;i<n;i++ ){
long long sum0=0;
for( int j=0;j<n;j++ ){
if(i==j) continue;
// long long val1= hammin( & )
// sum0+= max( hamming( &s[i],&s[j] ), hamming( &s[i], kontra(s[j]) ));
// sum1+=max( hamming( kontra( s[i] ), &s[j] ), hamming( kontra(s[i]),kontra(s[j]) ));
long long val1=hamming( i,j );
//cout << i << " " <<j << " " << val1<<endl;
if( val1 > n ) cout << " wtald cfffff "<<endl;
sum0+=min( val1, n-val1 );
// if( sum0>k && sum1>k )break;
if( sum0>k ) break;
}
// res=min( res, min( sum0,sum1 ) );
res=min( res, sum0 );
}
// cout<<res<< " aa " <<endl;
int pos=0;
if( n==k ){
//string curr=s[0];
for( int i=0;i<n;i++ ){
if( (i%64LL == 0 && i>0) )pos++;
/*if( curr[i]=='x' ){
block[pos]^=(1LL<<(i%64));
curr[i]='o';
}
else curr[i]='x';*/
block[0][pos]^=( 1LL<<(i%64LL) );
long long sum=0;
for( int j=0;j<n;j++ ){
if(i==j) continue;
long long val=hamming(0,j);
sum+=min( val, n-val );
}
res=min( res, sum );
block[0][pos]^=( 1LL<<(i%64LL) ); /// vratimo kako je bilo
}
}
if(res<=k) cout<<"DA"<<endl;
else cout<<"NE"<<endl;
// cout<<res<<endl;
return 0;
}
/*
5
1
2
1
2
2
*/
컴파일 시 표준 에러 (stderr) 메시지
sajam.cpp: In function 'long long int hamming(int, int)':
sajam.cpp:30:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i=0;i<block[a].size();i++ ){
~^~~~~~~~~~~~~~~~
sajam.cpp: In function 'int main()':
sajam.cpp:46:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int j=0;j<=s[i].size();j++ ){
~^~~~~~~~~~~~~
sajam.cpp:47:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if( ( j%c == 0 && j > 0 ) || j==s[i].size() ){
~^~~~~~~~~~~~~
sajam.cpp:50:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if( j==s[i].size() ) break;
~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |