oj.uz

Submission #120165

# Submission time Handle Problem Language Result Execution time Memory
120165 2019-06-23T16:04:19 Z OptxPrime Sajam (COCI18_sajam) C++11
45 / 90
 140 ms 2488 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< 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[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 );
            block[i][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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 14 ms 640 KB Output is correct
3 Correct 23 ms 896 KB Output is correct
4 Correct 85 ms 1400 KB Output is correct
5 Correct 23 ms 896 KB Output is correct
6 Correct 10 ms 512 KB Output is correct
7 Correct 15 ms 896 KB Output is correct
8 Correct 46 ms 1400 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 45 ms 1400 KB Output is correct

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 3 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1144 KB Output is correct
2 Correct 61 ms 1280 KB Output is correct
3 Correct 38 ms 1152 KB Output is correct
4 Correct 33 ms 1144 KB Output is correct
5 Correct 75 ms 1400 KB Output is correct
6 Correct 24 ms 896 KB Output is correct
7 Correct 48 ms 1272 KB Output is correct
8 Correct 60 ms 1328 KB Output is correct
9 Correct 10 ms 640 KB Output is correct
10 Correct 53 ms 2396 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1272 KB Output is correct
2 Correct 69 ms 1400 KB Output is correct
3 Correct 35 ms 1024 KB Output is correct
4 Correct 48 ms 1144 KB Output is correct
5 Correct 56 ms 1272 KB Output is correct
6 Correct 86 ms 2296 KB Output is correct
7 Correct 17 ms 640 KB Output is correct
8 Correct 45 ms 1144 KB Output is correct
9 Correct 31 ms 1288 KB Output is correct
10 Correct 52 ms 2364 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1080 KB Output is correct
2 Correct 49 ms 1140 KB Output is correct
3 Correct 128 ms 2424 KB Output is correct
4 Correct 31 ms 1272 KB Output is correct
5 Incorrect 49 ms 1500 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 2424 KB Output is correct
2 Correct 133 ms 2488 KB Output is correct
3 Correct 112 ms 1400 KB Output is correct
4 Incorrect 60 ms 1664 KB Output isn't correct
5 Halted 0 ms 0 KB -