| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 328869 |
2020-11-18T09:54:21 Z |
MonkeyKing |
Tram (CEOI13_tram) |
C++14 |
|
221 ms |
17516 KB |
//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
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);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
620 KB |
Output is correct |
| 2 |
Correct |
4 ms |
364 KB |
Output is correct |
| 3 |
Correct |
5 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
620 KB |
Output is correct |
| 2 |
Correct |
4 ms |
364 KB |
Output is correct |
| 3 |
Correct |
5 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
15084 KB |
Output is correct |
| 2 |
Correct |
4 ms |
364 KB |
Output is correct |
| 3 |
Correct |
88 ms |
15084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
15084 KB |
Output is correct |
| 2 |
Correct |
5 ms |
364 KB |
Output is correct |
| 3 |
Correct |
73 ms |
15084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
3024 KB |
Output is correct |
| 2 |
Correct |
75 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
99 ms |
2796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
221 ms |
17516 KB |
Output is correct |
| 2 |
Correct |
72 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
188 ms |
16108 KB |
Output is correct |
