1800O-R_Bust's blog

By 1800O-R_Bust, history, 10 days ago, In English

I cant figure out reason for TLE, code seems to be O(n) with some small constants, any help would be appreciated.

Problem Link : https://codeforces.com/contest/1251/problem/C

Code
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int INF = 4e5;
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
           
#define time__(d) \
    for ( \
        auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
        blockTime.second; \
        debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
    )


int get_num(int l[10],int y){
	int i;
	pi lp[10];
	for(i=0;i<=9;i++){
		lp[i]={l[i],i};
	}
	sort(lp,lp+10);
	for(auto [pos,el] : lp){
		if(pos!=INF && el>y){
			return el;
		}
	}
	return -1;
}
string run_filter(string x,int par){

	int n = x.length(),i,j;
	int leftmost_min[10];
	for(i=0;i<10;i++)
		leftmost_min[i]=INF;
	for(i=0;i<n;i++){
		leftmost_min[(x[i]-'0')]=min(leftmost_min[(x[i]-'0')],i);
		if(i>0 && ((x[i]-'0')%2==par) && ((x[i-1]-'0')%2!=par)){
			//cout<<x<<" "<<i<<" "<<x[i]<<endl;
			int cur=i,go;
		    go = get_num(leftmost_min,(x[i]-'0'));
			if(go!=-1){
				while(i>leftmost_min[go] && (x[i-1]%2)!=par){
					swap(x[i],x[i-1]);
					--i;
				}
				for(j=0;j<10;j++)
					leftmost_min[j]=INF;
				++i;
				while(i<=cur){
					leftmost_min[(x[i]-'0')]=min(leftmost_min[(x[i]-'0')],i);
					++i;
				}
				--i;
			}
		}
	}
	return x;
}

void run_case(){
	string s;
	cin >> s;
	//cout<<run_filter(s,1)<<endl;
	string ans1,ans2;
	time__("MAIN"){
		ans1 = run_filter(run_filter(s,1),0);
		//cout<<ans1<<endl;
		ans2 = run_filter(run_filter(s,0),1);
	}
	//cout<<ans2<<endl;
	if(ans1<ans2)
		cout << ans1;
	cout << ans2;
	cout<<"\n";
}
int main(){
	fast;	
	#ifndef ONLINE_JUDGE 
  
    // For getting input from input.txt file 
    freopen("example.txt", "r", stdin); 
  
    // Printing the Output to output.txt file 
    freopen("output.txt", "w", stdout); 
  
#endif 
	int t;
	cin >> t;
	while(t--){
		run_case();
	}	
}






Thanks!

Read more »

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

By 1800O-R_Bust, history, 4 months ago, In English

So I was thinking of making some div2B/C level CP problems for my school contest and thought of this....

Here it goes....

Find the maximum number of squares of side length 'a' that can completely be inscribed in a circle of radius 'r' such that exactly one of the vertices of the square touches the circle and no 2 squares overlap each other. Note that all the squares have to be completely inside the circle.

I cant figure this out..ended up taking too many variables which I cant eliminate...any thoughts or hints ?

The figure will look something like this :

Screenshot-106
No way am using geogebra for this

Apologize for the sketchy figure though.

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

By 1800O-R_Bust, history, 5 months ago, In English

I wanted to do a runtime analysis of B. It got AC even though I doubted it as it looked worst case O(n^2). Basically I just simulated what was asked. It is also mentioned in the editorial that simulation would take too much time. I am now really interested in the runtime of my code.

ARC-105_B

Also any ideas on D?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By 1800O-R_Bust, history, 5 months ago, In English

Why was CF down for a day? Is there some new feature that has been implemented or just maintanance?

Read more »

 
 
 
 
  • Vote: I like it
  • +158
  • Vote: I do not like it