oj.uz

Submission #120160

# Submission time Handle Problem Language Result Execution time Memory
120160 2019-06-23T15:51:12 Z OptxPrime Sajam (COCI18_sajam) C++11
0 / 90
 113 ms 3320 KB 
#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<unsigned 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 );
                    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 );
                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[i][pos]^=( 1LL<<(i%64LL) );
                    long long sum=0;
            for( int j=0;j<n;j++ ){
                if(i==j) continue;
                long long val=hamming(i,j);
                sum+=min( val, n-val );
            }
            res=min( res, sum );
            }
        }
        if(res<=k) cout<<"DA"<<endl;
        else cout<<"NE"<<endl;

    return 0;
}

/*
5
1
2
1

2
2
*/

Compilation message

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:49:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if( j==s[i].size() ) break;
                         ~^~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 10 ms 896 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 1792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 2028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 1536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 3320 KB Output isn't correct
2 Halted 0 ms 0 KB -