Submission #328869

#	Time	Username	Problem	Language	Result	Execution time	Memory
328869		MonkeyKing	Tram (CEOI13_tram)	C++14	100 / 100	221 ms	17516 KiB

tram

//Original Code:
//#include <self/utility>
//#include <self/debug>
//const ll sqrt2(2);
//using namespace std;
//
//int n,q;
//struct Scheme
//{
//	int x;
//	int y;
//	ll realLen;
//	Scheme(){}
//	Scheme(int _x,int _y,ll tLen):x(_x),y(_y),realLen(tLen){}
//	bool operator < (const Scheme &s)const&
//	{
//		if(realLen!=s.realLen) return realLen>s.realLen;
//		if(x!=s.x) return x<s.x;
//		return y<s.y;
//	}
//};
//
//struct Difference
//{
//	int m1,m2;
//	int st,ed;
//	// int ub,lb;
//	ll calc(int sx,int sy,int ex,int ey)const&
//	{
//		return 1LL*(ex-sx)*(ex-sx)+1LL*(ey-sy)*(ey-sy);
//	}
//	ll calc(int x,int y)const&
//	{
//		ll len=llinf;
//		if(m1!=-1)
//		{
//			if(m1&1) chmin(len,calc(st,0,x,y));
//			if(m1&2) chmin(len,calc(st,1,x,y));
//		}
//		if(m2!=-1)
//		{
//			if(m2&1) chmin(len,calc(ed,0,x,y));
//			if(m2&2) chmin(len,calc(ed,1,x,y));
//		}
//		return len;
//	}
//	static int resolve(int x)
//	{
//		if(x<0) x=0;
//		if(x>=n) x=n-1;
//		return x;
//	}
//	Scheme toScheme()const&
//	{
//		if(m1==-1 && m2==-1) return Scheme(0,0,inf);
//		assert(ed!=st);
//		if(ed-st==1)
//		{
//			if(m1==3 && m2==3) return Scheme(-1,-1,-inf);
//			if(!(m1&1)) return Scheme(st,0,1);
//			if(!(m2&1)) return Scheme(ed,0,1);
//			if(!(m1&2)) return Scheme(st,1,1);
//			if(!(m2&2)) return Scheme(ed,1,1);
//			assert(false);
//		}
//		int u=resolve((ed+st)>>1),d=resolve((ed+st+1)>>1);
//		ll len0=calc(u,0);
//		ll len1=calc(u,1);
//		ll len2=calc(d,0);
//		ll len3=calc(d,1);
//		ll maxv=max(max(len0,len2),max(len1,len3));
//		if(len0==maxv) return Scheme(u,0,len0);
//		if(len1==maxv) return Scheme(u,1,len1);
//		if(len2==maxv) return Scheme(d,0,len2);
//		if(len3==maxv) return Scheme(d,1,len3);
//		assert(false);
//	}
//	bool operator < (const Difference &d)const&
//	{
//		return toScheme()<d.toScheme();
//	}
//};
//char type[1];
//Scheme res[30005];
//int status[150005];
//set <int> squ;
//set <int> notUsed;
//set <Difference> diffs;
//
//Scheme query()
//{
//	Scheme t=diffs.begin()->toScheme();
//	if(t.realLen==1)
//	{
//		int t=*notUsed.begin();
//		return Scheme((t>>1),(t&1),1);
//	}
//	return diffs.begin()->toScheme();
//}
//
//Difference toDifference(int x,int y)
//{
//	Difference t;
//	if(x==-inf) t.m1=-1;else t.m1=status[x];
//	if(y==inf) t.m2=-1;else t.m2=status[y];
//	t.st=x;
//	t.ed=y;
//	return t;
//}
//
//void insert(int x,int y)
//{
//	diffs.insert(toDifference(x,y));
//}
//
//void erase(int x,int y)
//{
//	diffs.erase(toDifference(x,y));
//}
//
//void insert(Scheme t)
//{
//	int x=t.x;
//	int y=t.y;
//	notUsed.erase(x*2+y);
//	set <int> :: iterator nxt,pre,now;
//	if(squ.find(x)==squ.end())
//	{
//		nxt=squ.lower_bound(x);
//		pre=prev(nxt);
//		erase(*pre,*nxt);
//	}
//	else
//	{
//		now=squ.find(x);
//		pre=prev(now);
//		nxt=next(now);
//		erase(*pre,*now);
//		erase(*now,*nxt);
//	}
//	status[x]|=(1<<y);
//	squ.insert(x);
//	now=squ.find(x);
//	pre=prev(now);
//	nxt=next(now);
//	insert(*pre,*now);
//	insert(*now,*nxt);
//}
//
//void erase(Scheme t)
//{
//	set <int> :: iterator pre,now,nxt;
//	int x=t.x;
//	int y=t.y;
//	notUsed.insert(x*2+y);
//	now=squ.find(x);
//	pre=prev(now);
//	nxt=next(now);
//	erase(*pre,*now);
//	erase(*now,*nxt);
//	status[x]^=(1<<y);
//	if(status[x])
//	{
//		now=squ.find(x);
//		pre=prev(now);
//		nxt=next(now);
//		insert(*pre,*now);
//		insert(*now,*nxt);
//	}
//	else
//	{
//		squ.erase(x);
//		nxt=squ.lower_bound(x);
//		pre=prev(nxt);
//		insert(*pre,*nxt);
//	}
//}
//
//int main()
//{
//	// freopen("input.txt","r",stdin);
//	// freopen("output.txt","w",stdout);
//	scanf("%d%d",&n,&q);
//	for(int i=0;i<n*2;i++)
//	{
//		notUsed.insert(i);
//	}
//	squ.insert(-inf);
//	squ.insert(inf);
//	insert(-inf,inf);
//	// cout<<diffs.size()<<endl;
//	for(int i=0;i<q;i++)
//	{
//		scanf("%s",type);
//		if(type[0]=='E')
//		{
//			Scheme t=query();
//			res[i]=t;
//			insert(t);
//			printf("%d %d\n",t.x+1,t.y+1);
//		}
//		else
//		{
//			int t;
//			scanf("%d",&t);
//			t--;
//			erase(res[t]);
//		}
//	}
//	return 0;
//}

//substituted with C++ Inliner
#ifndef _SELF_UTILITY
#define _SELF_UTILITY 1
#include <numeric>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#include <assert.h>
#include <bitset>
#include <time.h>
#define Endl endl
#define mp make_pair
#define ll long long 
#define ull unsigned long long
#define pii pair<int,int>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define quickcin ios_base::sync_with_stdio(false);
#ifdef __TAKE_MOD
int mod;
#else
#ifdef __TAKE_CONST_MOD
const int mod=__TAKE_CONST_MOD;
#else
const int mod=1000000007;
#endif
#endif
const int gmod=5;
const int inf=1039074182;
const double eps=1e-9;
const ll llinf=2LL*inf*inf;
template <typename T1,typename T2> inline void chmin(T1 &x,T2 b) {if(b<x) x=b;}
template <typename T1,typename T2> inline void chmax(T1 &x,T2 b) {if(b>x) x=b;}
inline void chadd(int &x,int b) {x+=b-mod;x+=(x>>31 & mod);}
template <typename T1,typename T2> inline void chadd(T1 &x,T2 b) {x+=b;if(x>=mod) x-=mod;}
template <typename T1,typename T2> inline void chmul(T1 &x,T2 b) {x=1LL*x*b%mod;}
template <typename T1,typename T2> inline void chmod(T1 &x,T2 b) {x%=b,x+=b;if(x>=b) x-=b;}
template <typename T> inline T mabs(T x) {return (x<0?-x:x);}
#endif
using namespace std;
#ifndef _SELF_DEBUG
#define _SELF_DEBUG 1
#ifndef _SELF_OPERATOR
#define _SELF_OPERATOR 1
using namespace std;
template <typename T>
ostream &operator<<(ostream &cout, vector<T> vec)
{
	cout << "{";
	for (int i = 0; i < (int)vec.size(); i++)
	{
		cout << vec[i];
		if (i != (int)vec.size() - 1)
			cout << ',';
	}
	cout << "}";
	return cout;
}

template <typename T>
void operator*=(vector<T> &vec, int k)
{
	for (auto &x : vec)
		x *= k;
}

template <typename T>
void operator-=(vector<T> &a, const vector<T> &b)
{
	assert(a.size() == b.size());
	for (size_t it = 0; it < a.size(); it++)
	{
		a[it] -= b[it];
	}
}

template <typename T>
vector<T> operator*(const vector<T> &vec, int k)
{
	vector<T> res(vec);
	res *= k;
	return res;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &cout, pair<T1, T2> p)
{
	cout << "(" << p.first << ',' << p.second << ")";
	return cout;
}

template <typename T, typename T2>
ostream &operator<<(ostream &cout, set<T, T2> s)
{
	vector<T> t;
	for (auto x : s)
		t.push_back(x);
	cout << t;
	return cout;
}

template <typename T, typename T2>
ostream &operator<<(ostream &cout, multiset<T, T2> s)
{
	vector<T> t;
	for (auto x : s)
		t.push_back(x);
	cout << t;
	return cout;
}

template <typename T>
ostream &operator<<(ostream &cout, queue<T> q)
{
	vector<T> t;
	while (q.size())
	{
		t.push_back(q.front());
		q.pop();
	}
	cout << t;
	return cout;
}

template <typename T1, typename T2, typename T3>
ostream &operator<<(ostream &cout, map<T1, T2, T3> m)
{
	for (auto &x : m)
	{
		cout << "Key: " << x.first << ' ' << "Value: " << x.second << endl;
	}
	return cout;
}

template <typename T>
T operator*(vector<T> v1, vector<T> v2)
{
	assert(v1.size() == v2.size());
	int n = v1.size();
	T res = 0;
	for (int i = 0; i < n; i++)
	{
		res += v1[i] * v2[i];
	}
	return res;
}

template <typename T1, typename T2>
pair<T1, T2> operator+(pair<T1, T2> x, pair<T1, T2> y)
{
	return make_pair(x.first + y.first, x.second + y.second);
}

template <typename T1, typename T2>
void operator+=(pair<T1, T2> &x, pair<T1, T2> y)
{
	x.first += y.first;
	x.second += y.second;
}

template <typename T1, typename T2>
pair<T1, T2> operator-(pair<T1, T2> x)
{
	return make_pair(-x.first, -x.second);
}

template <typename T>
vector<vector<T>> operator~(vector<vector<T>> vec)
{
	vector<vector<T>> v;
	int n = vec.size(), m = vec[0].size();
	v.resize(m);
	for (int i = 0; i < m; i++)
	{
		v[i].resize(n);
	}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			v[i][j] = vec[j][i];
		}
	}
	return v;
}
#endif
void print0x(int x)
{
	std::vector <int> vec;
	while(x)
	{
		vec.push_back(x&1);
		x>>=1;
	}
	std::reverse(vec.begin(),vec.end());
	for(int i=0;i<(int)vec.size();i++)
	{
		std::cout<<vec[i];
	}
	std::cout<<' ';
}

template <typename T>
void print0x(T x,int len)
{
	std::vector <int> vec;
	while(x)
	{
		vec.push_back(x&1);
		x>>=1;
	}
	reverse(vec.begin(),vec.end());
	for(int i=(int)vec.size();i<len;i++)
	{
		putchar('0');
	}
	for(size_t i=0;i<vec.size();i++)
	{
		std::cout<<vec[i];
	}
	std::cout<<' ';
}
#endif
const ll sqrt2(2);
using namespace std;

int n,q;
struct Scheme
{
	int x;
	int y;
	ll realLen;
	Scheme(){}
	Scheme(int _x,int _y,ll tLen):x(_x),y(_y),realLen(tLen){}
	bool operator < (const Scheme &s)const&
	{
		if(realLen!=s.realLen) return realLen>s.realLen;
		if(x!=s.x) return x<s.x;
		return y<s.y;
	}
};

struct Difference
{
	int m1,m2;
	int st,ed;
	// int ub,lb;
	ll calc(int sx,int sy,int ex,int ey)const&
	{
		return 1LL*(ex-sx)*(ex-sx)+1LL*(ey-sy)*(ey-sy);
	}
	ll calc(int x,int y)const&
	{
		ll len=llinf;
		if(m1!=-1)
		{
			if(m1&1) chmin(len,calc(st,0,x,y));
			if(m1&2) chmin(len,calc(st,1,x,y));
		}
		if(m2!=-1)
		{
			if(m2&1) chmin(len,calc(ed,0,x,y));
			if(m2&2) chmin(len,calc(ed,1,x,y));
		}
		return len;
	}
	static int resolve(int x)
	{
		if(x<0) x=0;
		if(x>=n) x=n-1;
		return x;
	}
	Scheme toScheme()const&
	{
		if(m1==-1 && m2==-1) return Scheme(0,0,inf);
		assert(ed!=st);
		if(ed-st==1)
		{
			if(m1==3 && m2==3) return Scheme(-1,-1,-inf);
			if(!(m1&1)) return Scheme(st,0,1);
			if(!(m2&1)) return Scheme(ed,0,1);
			if(!(m1&2)) return Scheme(st,1,1);
			if(!(m2&2)) return Scheme(ed,1,1);
			assert(false);
		}
		int u=resolve((ed+st)>>1),d=resolve((ed+st+1)>>1);
		ll len0=calc(u,0);
		ll len1=calc(u,1);
		ll len2=calc(d,0);
		ll len3=calc(d,1);
		ll maxv=max(max(len0,len2),max(len1,len3));
		if(len0==maxv) return Scheme(u,0,len0);
		if(len1==maxv) return Scheme(u,1,len1);
		if(len2==maxv) return Scheme(d,0,len2);
		if(len3==maxv) return Scheme(d,1,len3);
		assert(false);
	}
	bool operator < (const Difference &d)const&
	{
		return toScheme()<d.toScheme();
	}
};
char type[1];
Scheme res[30005];
int status[150005];
set <int> squ;
set <int> notUsed;
set <Difference> diffs;

Scheme query()
{
	Scheme t=diffs.begin()->toScheme();
	if(t.realLen==1)
	{
		int t=*notUsed.begin();
		return Scheme((t>>1),(t&1),1);
	}
	return diffs.begin()->toScheme();
}

Difference toDifference(int x,int y)
{
	Difference t;
	if(x==-inf) t.m1=-1;else t.m1=status[x];
	if(y==inf) t.m2=-1;else t.m2=status[y];
	t.st=x;
	t.ed=y;
	return t;
}

void insert(int x,int y)
{
	diffs.insert(toDifference(x,y));
}

void erase(int x,int y)
{
	diffs.erase(toDifference(x,y));
}

void insert(Scheme t)
{
	int x=t.x;
	int y=t.y;
	notUsed.erase(x*2+y);
	set <int> :: iterator nxt,pre,now;
	if(squ.find(x)==squ.end())
	{
		nxt=squ.lower_bound(x);
		pre=prev(nxt);
		erase(*pre,*nxt);
	}
	else
	{
		now=squ.find(x);
		pre=prev(now);
		nxt=next(now);
		erase(*pre,*now);
		erase(*now,*nxt);
	}
	status[x]|=(1<<y);
	squ.insert(x);
	now=squ.find(x);
	pre=prev(now);
	nxt=next(now);
	insert(*pre,*now);
	insert(*now,*nxt);
}

void erase(Scheme t)
{
	set <int> :: iterator pre,now,nxt;
	int x=t.x;
	int y=t.y;
	notUsed.insert(x*2+y);
	now=squ.find(x);
	pre=prev(now);
	nxt=next(now);
	erase(*pre,*now);
	erase(*now,*nxt);
	status[x]^=(1<<y);
	if(status[x])
	{
		now=squ.find(x);
		pre=prev(now);
		nxt=next(now);
		insert(*pre,*now);
		insert(*now,*nxt);
	}
	else
	{
		squ.erase(x);
		nxt=squ.lower_bound(x);
		pre=prev(nxt);
		insert(*pre,*nxt);
	}
}

int main()
{
//	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=0;i<n*2;i++)
	{
		notUsed.insert(i);
	}
	squ.insert(-inf);
	squ.insert(inf);
	insert(-inf,inf);
	// cout<<diffs.size()<<endl;
	for(int i=0;i<q;i++)
	{
		scanf("%s",type);
		if(type[0]=='E')
		{
			Scheme t=query();
			res[i]=t;
			insert(t);
			printf("%d %d\n",t.x+1,t.y+1);
		}
		else
		{
			int t;
			scanf("%d",&t);
			t--;
			erase(res[t]);
		}
	}
	return 0;
}

Compilation message (stderr)

tram.cpp: In function 'int main()':
tram.cpp:624:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  624 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
tram.cpp:635:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  635 |   scanf("%s",type);
      |   ~~~~~^~~~~~~~~~~
tram.cpp:646:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  646 |    scanf("%d",&t);
      |    ~~~~~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 20 / 20