oj.uz

Submission #227158

# Submission time Handle Problem Language Result Execution time Memory
227158 2020-04-26T09:25:26 Z kshitij_sodani Konstrukcija (COCI20_konstrukcija) C++17
110 / 110
 6 ms 384 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"



int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo k;
	cin>>k;
	if(k==0){

		cout<<3<<" "<<2<<endl;
		cout<<1<<" "<<2<<endl;
		cout<<2<<" "<<3<<endl;
		return 0;
	}
	llo st=0;
	llo prod=1;
	vector<llo> ex;
	vector<vector<llo>> ac;
	ac.pb({1});
	llo ind=2;
	llo pre[61];
	pre[0]=1;
	for(llo i=1;i<61;i++){
		pre[i]=pre[i-1]*2;
	}
	int stt=0;
	if(k<0){
		k=-k;
		stt=1;
	}
//	cout<<pre[54]<<endl;
	for(llo i=60;i>=0;i--){
	//	cout<<(llo)(1<<i)<<endl;

		llo acc=(pre[i]&k);
		if(acc==(llo)0){
			if(st==0){
				continue;
			}
			else{
				ac.pb({ind,ind+1,ind+2});
				ind+=3;
				prod*=-2;
			}
		}
		else{
			if(st==0){
				st=1;

			}
			else{
				//ac.pb({ind,ind+1,ind+2});
				//prod*=2;
				if(prod<0){
					ac.pb({ind,ind+1});
					ind+=2;
					prod*=-1;
				}
				ac.pb({ind,ind+1,ind+2,ind+3});
				ind+=4;
				prod*=-2;
				prod-=1;
			}
		}
	}
	if(prod==k){
		ac.pb({ind,ind+1});
		ind+=2;
	}
	
	if(stt==1){
		ac.pb({ind,ind+1});
		ind+=2;
		
	}
	ac.pb({ind});
	ind+=1;
	vector<pair<llo,llo>> ans;
	for(llo i=1;i<ac.size();i++){
		for(llo j=0;j<min((llo)3,(llo)ac[i].size());j++){
			for(auto k:ac[i-1]){
				ans.pb({k,ac[i][j]});
			}
		}
		if(ac[i].size()==4){
			ans.pb({1,ac[i][3]});
		}
	}
	if(ind-1>1000 or ans.size()>1000){
		while(true){
			continue;
		}
	}
	cout<<ind-1<<" "<<ans.size()<<endl;
	for(auto j:ans){
		cout<<j.a<<" "<<j.b<<endl;
	}





	return 0;
}

Compilation message

konstrukcija.cpp: In function 'int main()':
konstrukcija.cpp:89:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llo i=1;i<ac.size();i++){
              ~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correct.
2 Correct 5 ms 384 KB Correct.
3 Correct 5 ms 384 KB Correct.
4 Correct 5 ms 384 KB Correct.
5 Correct 4 ms 384 KB Correct.

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Correct.
2 Correct 5 ms 384 KB Correct.
3 Correct 6 ms 384 KB Correct.
4 Correct 4 ms 384 KB Correct.
5 Correct 5 ms 384 KB Correct.

Subtask #3
20.0 / 20.0

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

Subtask #4
60.0 / 60.0

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