1800O-R_Bust's blog

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

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

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!

• -1

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

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 :

Apologize for the sketchy figure though.

• +4

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

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?

• 0

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

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