Submission #222617

#	Time	Username	Problem	Language	Result	Execution time	Memory
222617		jamielim	Popcount (COCI19_popcount)	C++14	110 / 110	57 ms	636 KiB

popcount

#include <bits/stdc++.h>
using namespace std;

string precomp[505];
int n,k;

string add(string a,string b){
	string ans="";
	int carry=0;
	int la=(int)a.length(),lb=(int)b.length();
	if(la>lb){
		swap(la,lb);
		swap(a,b);
	}
	for(int i=0;i<la;i++){
		int A=a[la-i-1]-'0',B=b[lb-i-1]-'0';
		ans=ans+(char)((A+B+carry)%10+'0');
		if(A+B+carry>=10)carry=1;
		else carry=0;
	}
	for(int i=la;i<lb;i++){
		int B=b[lb-i-1]-'0'; //A=0
		ans=ans+(char)((B+carry)%10+'0');
		if(B+carry>=10)carry=1;
		else carry=0;
	}
	if(carry==1)ans=ans+"1";
	reverse(ans.begin(),ans.end());
	return ans;
}

string lol(long long seglen,int parity){
	string ans="0";
	if(parity==0){
		for(int i=0;i<n;i++){
			if((i/seglen)%2==0)ans=add(ans,precomp[i]);
		}
	}else{
		for(int i=0;i<n;i++){
			if((i/seglen)%2==1)ans=add(ans,precomp[i]);
		}
	}
	return ans;
}

int main(){
	precomp[0]="1";
	for(int i=1;i<505;i++){
		precomp[i]=add(precomp[i-1],precomp[i-1]);
	}
	scanf("%d%d",&n,&k);
	vector<string> ans;
	for(long long i=0;i<k;i++){
		if((1LL<<i)>n)break;
		string s1=lol(1LL<<i,0),s2=lol(1LL<<i,1);
		ans.push_back("A=((A&"+s1+")+((A&"+s2+")>>(1<<"+to_string(i)+")))\n");
	}
	printf("%d\n",(int)ans.size());
	for(int i=0;i<(int)ans.size();i++)printf("%s",ans[i].c_str());
}

Compilation message (stderr)

popcount.cpp: In function 'int main()':
popcount.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45