oj.uz

Submission #120166

# Submission time Handle Problem Language Result Execution time Memory
120166 2019-06-23T16:07:26 Z OptxPrime Sajam (COCI18_sajam) C++11
90 / 90
 142 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< 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

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 15 ms 640 KB Output is correct
3 Correct 23 ms 1024 KB Output is correct
4 Correct 88 ms 1400 KB Output is correct
5 Correct 24 ms 1020 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 14 ms 896 KB Output is correct
8 Correct 44 ms 1400 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 45 ms 1400 KB Output is correct

Subtask #2
15.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 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1144 KB Output is correct
2 Correct 70 ms 1236 KB Output is correct
3 Correct 38 ms 1172 KB Output is correct
4 Correct 33 ms 1024 KB Output is correct
5 Correct 76 ms 1400 KB Output is correct
6 Correct 24 ms 1016 KB Output is correct
7 Correct 49 ms 1244 KB Output is correct
8 Correct 55 ms 1272 KB Output is correct
9 Correct 10 ms 640 KB Output is correct
10 Correct 53 ms 2444 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 1400 KB Output is correct
2 Correct 72 ms 1372 KB Output is correct
3 Correct 35 ms 1152 KB Output is correct
4 Correct 50 ms 1328 KB Output is correct
5 Correct 50 ms 1152 KB Output is correct
6 Correct 92 ms 2436 KB Output is correct
7 Correct 18 ms 640 KB Output is correct
8 Correct 47 ms 1216 KB Output is correct
9 Correct 31 ms 1272 KB Output is correct
10 Correct 51 ms 2424 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1152 KB Output is correct
2 Correct 49 ms 1024 KB Output is correct
3 Correct 130 ms 2424 KB Output is correct
4 Correct 30 ms 1016 KB Output is correct
5 Correct 48 ms 1152 KB Output is correct
6 Correct 139 ms 3320 KB Output is correct
7 Correct 31 ms 1272 KB Output is correct
8 Correct 34 ms 1400 KB Output is correct
9 Correct 30 ms 1280 KB Output is correct
10 Correct 29 ms 1280 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 2424 KB Output is correct
2 Correct 135 ms 2292 KB Output is correct
3 Correct 116 ms 1344 KB Output is correct
4 Correct 62 ms 1152 KB Output is correct
5 Correct 62 ms 1784 KB Output is correct
6 Correct 69 ms 1792 KB Output is correct
7 Correct 31 ms 1280 KB Output is correct
8 Correct 112 ms 2296 KB Output is correct
9 Correct 41 ms 1528 KB Output is correct
10 Correct 99 ms 2388 KB Output is correct