Submission #274800

#	Time	Username	Problem	Language	Result	Execution time	Memory
274800		arnold518	Tram (CEOI13_tram)	C++14	65 / 100	1076 ms	876 KiB

tram

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;
const int MAXM = 3e4;

int N, M, A[MAXN+10];
pii ans[MAXN+10];
set<int> S1, S2;

ll dist(ll x1, ll y1, ll x2, ll y2)
{
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++)
	{
		char c;
		scanf(" %c", &c);
		if(c=='E') A[i]=-1;
		else scanf("%d", &A[i]);
	}

	for(int i=1; i<=M; i++)
	{
		if(A[i]==-1)
		{
			ll val=-1; int y, x;

			map<int, int> M;
			for(auto it : S1) M[it]+=1;
			for(auto it : S2) M[it]+=2;
			if(M.empty())
			{
				y=1; x=1;
				ans[i]={x, y};
				if(y==1) S1.insert(x);
				else S2.insert(x);
				printf("%d %d\n", x, y);
				continue;
			}

			for(auto it=M.begin(); next(it)!=M.end(); it++)
			{
				auto jt=next(it);
				int x1=it->first, x2=jt->first;
				int y1=it->second, y2=jt->second;
				if(y1==3) y1=1; if(y2==3) y2=1;
				if(y1==y2)
				{
					int nx=(x1+x2)/2, ny=1;
					ll now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
					if(val<now) val=now, x=nx, y=ny;
					else if(val==now)
					{
						if(nx<x) x=nx, y=ny;
						else if(nx==x && ny<y) y=ny;
					}
				}
				else
				{
					int nx=(x1+x2)/2, ny=1;
					ll now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
					if(val<now) val=now, x=nx, y=ny;
					else if(val==now)
					{
						if(nx<x) x=nx, y=ny;
						else if(nx==x && ny<y) y=ny;
					}
					nx=(x1+x2)/2+1, ny=1;
					now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
					if(val<now) val=now, x=nx, y=ny;
					else if(val==now)
					{
						if(nx<x) x=nx, y=ny;
						else if(nx==x && ny<y) y=ny;
					}
				}
			}

			for(auto it=M.begin(); next(it)!=M.end(); it++)
			{
				auto jt=next(it);
				int x1=it->first, x2=jt->first;
				int y1=it->second, y2=jt->second;
				if(y1==3) y1=2; if(y2==3) y2=2;
				if(y1==y2)
				{
					int nx=(x1+x2)/2, ny=2;
					ll now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
					if(val<now) val=now, x=nx, y=ny;
					else if(val==now)
					{
						if(nx<x) x=nx, y=ny;
						else if(nx==x && ny<y) y=ny;
					}
				}
				else
				{
					int nx=(x1+x2)/2, ny=2;
					ll now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
					if(val<now) val=now, x=nx, y=ny;
					else if(val==now)
					{
						if(nx<x) x=nx, y=ny;
						else if(nx==x && ny<y) y=ny;
					}
					nx=(x1+x2)/2+1, ny=2;
					now=min(dist(nx, ny, x1, y1), dist(nx, ny, x2, y2));
					if(val<now) val=now, x=nx, y=ny;
					else if(val==now)
					{
						if(nx<x) x=nx, y=ny;
						else if(nx==x && ny<y) y=ny;
					}
				}
			}

			{
				int x1=M.begin()->first, y1=M.begin()->second;
				if(y1==3) y1=1;
				int nx=1, ny=1;
				ll now=dist(nx, ny, x1, y1);
				if(val<now) val=now, x=nx, y=ny;
				else if(val==now)
				{
					if(nx<x) x=nx, y=ny;
					else if(nx==x && ny<y) y=ny;
				}
			}
			{
				int x1=M.begin()->first, y1=M.begin()->second;
				if(y1==3) y1=2;
				int nx=1, ny=2;
				ll now=dist(nx, ny, x1, y1);
				if(val<now) val=now, x=nx, y=ny;
				else if(val==now)
				{
					if(nx<x) x=nx, y=ny;
					else if(nx==x && ny<y) y=ny;
				}
			}
			{
				int x1=(--M.end())->first, y1=(--M.end())->second;
				if(y1==3) y1=1;
				int nx=N, ny=1;
				ll now=dist(nx, ny, x1, y1);
				if(val<now) val=now, x=nx, y=ny;
				else if(val==now)
				{
					if(nx<x) x=nx, y=ny;
					else if(nx==x && ny<y) y=ny;
				}
			}
			{
				int x1=(--M.end())->first, y1=(--M.end())->second;
				if(y1==3) y1=2;
				int nx=N, ny=2;
				ll now=dist(nx, ny, x1, y1);
				if(val<now) val=now, x=nx, y=ny;
				else if(val==now)
				{
					if(nx<x) x=nx, y=ny;
					else if(nx==x && ny<y) y=ny;
				}
			}

			ans[i]={x, y};
			if(y==1) S1.insert(x);
			else S2.insert(x);
			printf("%d %d\n", x, y);
		}
		else
		{
			int x=ans[A[i]].first, y=ans[A[i]].second;
			if(y==1) S1.erase(x);
			else S2.erase(x);
		}
	}
}

Compilation message (stderr)

tram.cpp: In function 'int main()':
tram.cpp:55:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   55 |     if(y1==3) y1=1; if(y2==3) y2=1;
      |     ^~
tram.cpp:55:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   55 |     if(y1==3) y1=1; if(y2==3) y2=1;
      |                     ^~
tram.cpp:93:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   93 |     if(y1==3) y1=2; if(y2==3) y2=2;
      |     ^~
tram.cpp:93:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   93 |     if(y1==3) y1=2; if(y2==3) y2=2;
      |                     ^~
tram.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |   scanf(" %c", &c);
      |   ~~~~~^~~~~~~~~~~
tram.cpp:28:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |   else scanf("%d", &A[i]);
      |        ~~~~~^~~~~~~~~~~~~

• 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: 0 / 15
• Subtask 8: 0 / 20