Submission #735149

#	Time	Username	Problem	Language	Result	Execution time	Memory
735149		NemanjaSo2005	Council (JOI23_council)	C++14	0 / 100	3 ms	4436 KiB

council

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,M,K,kol[25],maks[300005],res[300005],niz[300005],a,dist[1050000],stepen[25];
void rek1(int dub,int br,int nbroj,int cena,int koji){
   if(dub==K+1){
      cout<<br<<" postaje "<<nbroj<<" za "<<cena<<endl;
      res[koji]=min(res[koji],cena+dist[nbroj]);
      return;
   }
   if(br&stepen[dub])
      rek1(dub+1,br,nbroj,cena+1,koji);
   else
      rek1(dub+1,br,nbroj,cena,koji);
   rek1(dub+1,br,nbroj+stepen[dub],cena,koji);
}
void rek2(int dub,int obr,int nbroj,int cena){
   if(dub==M){
      cout<<obr<<" ide u "<<nbroj<<" cenom "<<cena<<endl;
      dist[nbroj]=min(dist[nbroj],cena);
      return;
   }
   if(obr&stepen[dub])
      rek2(dub+1,obr,nbroj,cena+1);
   else
      rek2(dub+1,obr,nbroj,cena);
   rek2(dub+1,obr,nbroj+stepen[dub],cena);
}
void dodaj(int br){
   for(int i=0;i<M;i++)
      br^=stepen[i];
   rek2(K+1,br,br&(stepen[K+1]-1),0);
}
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   for(int i=0;i<=1048576;i++)
      dist[i]=100;
   cin>>N>>M;
   stepen[0]=1;
   for(int i=1;i<=M+2;i++)
      stepen[i]=stepen[i-1]*2;
   for(int i=1;i<=N;i++){
      for(int j=1;j<=M;j++){
         niz[i]<<=1;
         cin>>a;
         niz[i]|=a;
      }
   }
   for(int i=1;i<=N;i++){
      for(int j=0;j<M;j++)
         if(niz[i]&stepen[j])
            kol[j]++;
   }
   for(int i=1;i<=N;i++){
      for(int j=0;j<M;j++)
         if(niz[j]&stepen[j])
            kol[j]--;
      for(int j=M-1;j>=0;j--)
         if(kol[j]>=(N-2)/2+1)
            maks[i]++;
      res[i]=maks[i];
      for(int j=0;j<M;j++)
         if(niz[j]&stepen[j])
            kol[j]++;
   }
   K=(M-1)/2;

   for(int i=1;i<=N;i++){
      for(int j=0;j<M;j++)
         if(niz[j]&stepen[j])
            kol[j]--;
      int br=0;
      for(int j=M-1;j>=0;j--){
         if(kol[j]==(N-2)/2+1)
            br+=1;
         br<<=1;
      }
      rek1(0,niz[i],0,0,i);
      dodaj(niz[i]);
      for(int j=0;j<M;j++)
         if(niz[j]&stepen[j])
            kol[j]++;
   }
/*   for(int i=0;i<=1048576;i++)
      dist[i]=100;
   for(int i=N;i>=1;i--){
      for(int j=0;j<M;j++)
         if(niz[j]&stepen[j])
            kol[j]--;
      int br=0;
      for(int j=M-1;j>=0;j--){
         if(kol[j]==(N-2)/2+1)
            br+=1;
         br<<=1;
      }
      rek1(0,niz[i],0,0,i);
      dodaj(niz[i]);
      for(int j=0;j<M;j++)
         if(niz[j]&stepen[j])
            kol[j]++;
   }*/
   for(int i=1;i<=N;i++)
      cout<<maks[i]<<" ";
   cout<<"\n";
   for(int i=1;i<=N;i++)
      cout<<res[i]<<" ";
   cout<<"\n";
   for(int i=1;i<=N;i++)
      cout<<maks[i]-res[i]<<"\n";
   return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 8
• Subtask 3: 0 / 6
• Subtask 4: 0 / 19
• Subtask 5: 0 / 15
• Subtask 6: 0 / 22
• Subtask 7: 0 / 22