Submission #120127

#TimeUsernameProblemLanguageResultExecution timeMemory
120127OptxPrimeSajam (COCI18_sajam)C++11
60 / 90
325 ms23032 KiB
#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 unsigned long long n,k; unsigned long long c=64; string s[2010]; unsigned long long dist[2010][2010][2]; unsigned long long spec[2010][2]; vector<unsigned long long>block[2010]; /// ovo bi trebalo da rjesi sve osim K=N /// nesto ne valja, mozda mi treba unsigned long long unsigned long long hamming( int a, int b ) { unsigned long long ans=0; for( int i=0;i<block[a].size();i++ ){ // cout << a << " " << b << " " << i << " "<< block[a][i] << " tarik " <<endl; ans+= (unsigned long long)(__builtin_popcountll( block[a][i]^block[b][i] )); } return ans; } string kontra( string s ) { string ans=""; ans.resize(n); for( int i=0;i<n;i++ ){ if( s[i]=='x' ) ans[i]='o'; else ans[i]='x'; } return ans; } int main() { cin>>n>>k; //cout << kontra( "xoxx" )<<endl; // // cout<<" pasha " <<endl; for( int i=0;i<4*n;i++ ){ // cout<<i<<" lalala " <<endl; if( i<n ) cin>>s[i]; else if( i<2*n ) s[i]=kontra( s[i-n] ); else if( i<3*n ){ /// ubacujemo izmjene if( n!=k ) break; s[i]=s[0]; if(s[i][i-2*n] == 'x') s[i][i-2*n]='o'; else s[i][ i-2*n ]='x'; } else{ /// opet izmjenr s[i]= kontra( s[0] ); if( s[i][ i-3*n ]=='x' ) s[i][ i-3*n ]='o'; else s[i][ i-3*n ]='x'; } unsigned long long curr=0; for( unsigned long long j=0;j<=n;j++ ){ // cout <<j<< " aa " <<endl; /// c je velicina bloka, 64 if( (j%c==0 && j>0) || ( j==n ) ){ // if( i==0 ) cout<< j << " " <<curr << " wtf "<<endl; block[i].pb( curr ); curr=0LL; if(j==n) break; } if( s[i][j]=='x' ) { curr|=( 1LL<<( j%c ) ); // cout << i << " " << j << " " << ( j%64 ) << " namir " <<endl; } } } /* 3 3 xxo xox oox */ /// treba jos postaviti od prvog stringa sve izmjene // cout << block[3*n][0] << " " << block[3*n+1][2] << " kontas " <<endl; /// dobri svi blokovi izgleda /* string curr=s[0]; for( int i=0;i<n;i++ ){ }*/ //cout << block[1][0] << " eto " <<endl; unsigned long long res=100000000; for( int i=0;i<n;i++ ){ unsigned long long sum0=0,sum1=0; for( int j=0;j<n;j++ ){ if( i==j ) continue; if( n==k && i==0 ){ /// ovo je specijalan slucaj kad mozemo u svakom redu promjenit /// ne valja mi ovo for( int p=0;p<n;p++ ){ unsigned long long sum0=0,sum1=0; for( int a=0;a<n;a++ ){ spec[a][0]=spec[a][1]=100000000; spec[a][0]= hamming( 2*n+p,a ); spec[a][0]=min( spec[a][0], hamming( 2*n+p,n+a ) ); spec[a][1]= hamming( 3*n+p,a ); spec[a][1]=min(spec[a][1],hamming( 3*n+p,n+a )); sum0+=spec[a][0]; sum1+=spec[a][1]; } if( sum0 <= k || sum1<=k ){ // cout << sum0 <<" " << sum1 << " bee " <<endl; cout<<"DA"<<endl; return 0; } } } dist[i][j][0] = hamming( i,j ); // string tmp= kontra( ) ; dist[i][j][0]=min( dist[i][j][0], hamming( i,j+n ) ); dist[i][j][1]= hamming( i+n,j ); dist[i][j][1]=min( dist[i][j][1], hamming( i+n,j+n )); // cout<<i << " " << j << " " << dist[i][j][0] << " " << dist[i][j][1] << " tjt " <<endl; sum0+=dist[i][j][0]; sum1+=dist[i][j][1]; } res=min( res,sum0 ); res=min(res,sum1); } // for( int i=0;i<n;i++ ) cout<<block[i][0] << " rastika " <<endl; // cout<<res<<endl; if( res<=k ) cout<<"DA"<<endl; else cout<<"NE"<<endl; /* for( int i=0;i<n;i++ ){ for( int j=0;j<n;j++ ){ if(i==j)continue; unsigned long long tmp=0,anss; for( int k=0;k<n;k++ ){ if( s[i][k]!=s[j][k] ) tmp++; } anss=tmp; tmp=0; string t=kontra( s[j] ); /* if( i==0 ){ cout<<s[j]<<endl; cout<<t<<endl; cout<<" roogibe " <<endl; } for( int k=0;k<n;k++ ){ if( s[i][k]!=t[k] ) tmp++; } anss=min( anss, tmp ); // cout<<i<<" " << j << " " << dist[i][j][0] << " "<< anss << " aaa bukovica " <<endl; /// ne poklapa se dist[i][j] uvijek sa anss iz nekog razloga. } }*/ return 0; } /* 5 1 2 1 2 2 */

Compilation message (stderr)

sajam.cpp:158:8: warning: "/*" within comment [-Wcomment]
        /* if( i==0 ){
         
sajam.cpp: In function 'long long unsigned 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 'std::__cxx11::string kontra(std::__cxx11::string)':
sajam.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int i=0;i<n;i++ ){
                      ~^~
sajam.cpp: In function 'int main()':
sajam.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i=0;i<4*n;i++ ){
                  ~^~~~
sajam.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if( i<n )
                 ~^~
sajam.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             else if( i<2*n ) s[i]=kontra( s[i-n] );
                      ~^~~~
sajam.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             else if( i<3*n ){   /// ubacujemo izmjene
                      ~^~~~
sajam.cpp:102:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i=0;i<n;i++ ){
                  ~^~
sajam.cpp:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for( int j=0;j<n;j++ ){
                      ~^~
sajam.cpp:110:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         for( int p=0;p<n;p++ ){
                                      ~^~
sajam.cpp:112:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                             for( int a=0;a<n;a++ ){
                                          ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...