Submission #120166

#	Time	Username	Problem	Language	Result	Execution time	Memory
120166		OptxPrime	Sajam (COCI18_sajam)	C++11	90 / 90	142 ms	3320 KiB

sajam

#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
*/

Compilation message (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;
                         ~^~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 15 / 15