oj.uz

Submission #222617

# Submission time Handle Problem Language Result Execution time Memory
222617 2020-04-13T12:39:25 Z jamielim Popcount (COCI19_popcount) C++14
110 / 110
 57 ms 636 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 12 ms 384 KB Accepted.
2 Correct 10 ms 384 KB Accepted.
3 Correct 10 ms 384 KB Accepted.
4 Correct 10 ms 384 KB Accepted.
5 Correct 10 ms 384 KB Accepted.
6 Correct 10 ms 384 KB Accepted.
7 Correct 10 ms 384 KB Accepted.
8 Correct 10 ms 512 KB Accepted.
9 Correct 10 ms 384 KB Accepted.
10 Correct 10 ms 384 KB Accepted.
11 Correct 10 ms 512 KB Accepted.
12 Correct 10 ms 384 KB Accepted.
13 Correct 10 ms 384 KB Accepted.
14 Correct 10 ms 512 KB Accepted.

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 384 KB Accepted.

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 384 KB Accepted.
2 Correct 10 ms 384 KB Accepted.
3 Correct 10 ms 384 KB Accepted.
4 Correct 10 ms 512 KB Accepted.
5 Correct 10 ms 384 KB Accepted.
6 Correct 10 ms 384 KB Accepted.
7 Correct 10 ms 384 KB Accepted.
8 Correct 10 ms 384 KB Accepted.
9 Correct 10 ms 384 KB Accepted.
10 Correct 11 ms 384 KB Accepted.
11 Correct 10 ms 384 KB Accepted.
12 Correct 10 ms 384 KB Accepted.
13 Correct 10 ms 384 KB Accepted.
14 Correct 10 ms 384 KB Accepted.
15 Correct 10 ms 384 KB Accepted.
16 Correct 10 ms 512 KB Accepted.
17 Correct 10 ms 384 KB Accepted.
18 Correct 10 ms 384 KB Accepted.
19 Correct 10 ms 384 KB Accepted.
20 Correct 10 ms 384 KB Accepted.
21 Correct 10 ms 384 KB Accepted.

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 636 KB Accepted.
2 Correct 26 ms 384 KB Accepted.
3 Correct 42 ms 504 KB Accepted.
4 Correct 53 ms 384 KB Accepted.
5 Correct 15 ms 384 KB Accepted.
6 Correct 11 ms 384 KB Accepted.
7 Correct 12 ms 384 KB Accepted.
8 Correct 12 ms 384 KB Accepted.
9 Correct 18 ms 384 KB Accepted.
10 Correct 19 ms 384 KB Accepted.
11 Correct 21 ms 384 KB Accepted.
12 Correct 56 ms 384 KB Accepted.