QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56057 | #2428. Comma Sprinkler | captured# | AC ✓ | 655ms | 48636kb | C++ | 3.9kb | 2022-10-16 18:21:50 | 2022-10-16 18:21:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ff first
#define sn second
#define READ freopen("in.txt","r",stdin)
#define WRITE freopen("out.txt","w",stdout);
#define endl "\n"
#define lnd tree[ind<<1]
#define rnd tree[(ind<<1)+1]
#define cnd tree[ind]
#define lndp b,(b+e)>>1,(ind<<1)
#define rndp ((b+e)>>1)+1,e,(ind<<1)+1
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pLL;
const int mx2=2000005;
const int mod=998244353;
const long double EPS=1e-12;
int dir[4][2]={1,0,-1,0,0,-1,0,1};
//ll fact[mx];
//ll bigmod(ll n, ll p)
//{
// if(p==0)
// return 1;
// if(p%2==0)
// {
// ll x=bigmod(n,p/2);
// return (x*x)%mod;
// }
// else
// {
// ll x=bigmod(n,p-1);
// return (x*n)%mod;
// }
//}
const int mx=2000011;
vector<string>v;
int mark[mx];
int mark_end[mx];
map<string, vector<int> > mp;
int etarpor[mx];
int etarage[mx];
int main()
{
SPEED;
//
int t=1,tc=1;
// cin >> t;
while(t--)
{
// cout << "ok" << endl;
string s;
getline(cin , s);
int len = s.length();
int now = 1;
int cnt = 0;
string tmp = "";
for(int i = 0 ; i < len; i++)
{
if(s[i] == ' ')
{
v.push_back(tmp);
int tmp_len = tmp.size();
tmp = "";
}
else
tmp += s[i];
}
v.push_back(tmp);
mark[0] = 1;
queue<pair<string, int> >q;
map<pair<string , int> , int > vis;
for(int i = 0 ; i < v.size(); i++)
{
tmp = v[i];
int tmp_len = tmp.size();
string tmp2 = tmp;
if(tmp[tmp_len - 1] == '.')
{
mark[i + 1] = 1;
tmp2.pop_back();
mark_end[i] = 1;
}
else if(tmp[tmp_len - 1] == ',')
{
tmp2.pop_back();
if(vis.find({tmp2,0}) == vis.end()){
q.push({tmp2, 0});
vis[{tmp2,0}];
}
}
v[i] = tmp2;
// cout << v[i] << endl;
mp[tmp2].push_back(i);
}
// cout << "ok" << endl;
int v_sz = v.size();
while(!q.empty())
{
auto node = q.front();
q.pop();
tmp = node.ff;
int flag = node.sn;
if(flag == 0)
{
for(auto x : mp[tmp])
{
if(mark_end[x] == 1)
continue;
etarpor[x] = 1;
if(x + 1 >= v_sz)
continue;
string tmp2 = v[x + 1];
if(vis.find({tmp2, 1}) == vis.end())
{
q.push({tmp2, 1});
vis[{tmp2, 1}] = 1;
}
}
}
else
{
for(auto x : mp[tmp])
{
if(mark[x] == 1)
continue;
etarage[x] = 1;
if(x - 1 < 0)
continue;
string tmp2 = v[x - 1];
if(vis.find({tmp2, 0}) == vis.end())
{
q.push({tmp2, 0});
vis[{tmp2, 0}] = 1;
}
}
}
}
for(int i = 0 ; i < v_sz; i++)
{
if(i == 0)
{
cout << v[i];
if(etarpor[i])
cout << ",";
else if(mark_end[i])
cout << ".";
}
else
{
cout << " ";
cout << v[i];
if(etarpor[i])
cout << ",";
else if(mark_end[i])
cout << ".";
}
}
}
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 3ms
memory: 9708kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 9808kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 7680kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 7796kb
Test #5:
score: 0
Accepted
time: 2ms
memory: 9668kb
Test #6:
score: 0
Accepted
time: 74ms
memory: 30316kb
Test #7:
score: 0
Accepted
time: 164ms
memory: 37952kb
Test #8:
score: 0
Accepted
time: 169ms
memory: 37268kb
Test #9:
score: 0
Accepted
time: 1ms
memory: 9896kb
Test #10:
score: 0
Accepted
time: 0ms
memory: 9804kb
Test #11:
score: 0
Accepted
time: 3ms
memory: 9844kb
Test #12:
score: 0
Accepted
time: 2ms
memory: 7620kb
Test #13:
score: 0
Accepted
time: 3ms
memory: 9784kb
Test #14:
score: 0
Accepted
time: 3ms
memory: 9880kb
Test #15:
score: 0
Accepted
time: 3ms
memory: 9740kb
Test #16:
score: 0
Accepted
time: 203ms
memory: 27228kb
Test #17:
score: 0
Accepted
time: 344ms
memory: 32760kb
Test #18:
score: 0
Accepted
time: 577ms
memory: 48056kb
Test #19:
score: 0
Accepted
time: 1ms
memory: 9752kb
Test #20:
score: 0
Accepted
time: 554ms
memory: 46056kb
Test #21:
score: 0
Accepted
time: 273ms
memory: 40268kb
Test #22:
score: 0
Accepted
time: 228ms
memory: 35608kb
Test #23:
score: 0
Accepted
time: 23ms
memory: 15860kb
Test #24:
score: 0
Accepted
time: 589ms
memory: 47512kb
Test #25:
score: 0
Accepted
time: 655ms
memory: 48636kb
Test #26:
score: 0
Accepted
time: 300ms
memory: 36912kb
Test #27:
score: 0
Accepted
time: 121ms
memory: 28328kb
Test #28:
score: 0
Accepted
time: 501ms
memory: 44872kb
Test #29:
score: 0
Accepted
time: 8ms
memory: 12968kb
Test #30:
score: 0
Accepted
time: 4ms
memory: 9780kb
Test #31:
score: 0
Accepted
time: 2ms
memory: 10808kb
Test #32:
score: 0
Accepted
time: 5ms
memory: 15416kb
Test #33:
score: 0
Accepted
time: 2ms
memory: 7796kb
Test #34:
score: 0
Accepted
time: 4ms
memory: 9704kb
Test #35:
score: 0
Accepted
time: 3ms
memory: 9792kb
Test #36:
score: 0
Accepted
time: 3ms
memory: 9848kb
Test #37:
score: 0
Accepted
time: 1ms
memory: 9780kb
Test #38:
score: 0
Accepted
time: 3ms
memory: 9724kb
Test #39:
score: 0
Accepted
time: 0ms
memory: 9664kb
Test #40:
score: 0
Accepted
time: 0ms
memory: 9752kb
Test #41:
score: 0
Accepted
time: 4ms
memory: 11392kb
Test #42:
score: 0
Accepted
time: 12ms
memory: 11348kb
Test #43:
score: 0
Accepted
time: 10ms
memory: 11044kb
Test #44:
score: 0
Accepted
time: 5ms
memory: 11400kb
Test #45:
score: 0
Accepted
time: 5ms
memory: 11356kb
Test #46:
score: 0
Accepted
time: 11ms
memory: 11404kb
Test #47:
score: 0
Accepted
time: 88ms
memory: 20300kb
Test #48:
score: 0
Accepted
time: 97ms
memory: 20588kb
Test #49:
score: 0
Accepted
time: 92ms
memory: 20100kb
Test #50:
score: 0
Accepted
time: 66ms
memory: 17336kb
Test #51:
score: 0
Accepted
time: 63ms
memory: 17384kb
Test #52:
score: 0
Accepted
time: 57ms
memory: 18296kb
Test #53:
score: 0
Accepted
time: 180ms
memory: 24264kb
Test #54:
score: 0
Accepted
time: 176ms
memory: 24100kb
Test #55:
score: 0
Accepted
time: 166ms
memory: 24168kb
Test #56:
score: 0
Accepted
time: 137ms
memory: 22452kb
Test #57:
score: 0
Accepted
time: 157ms
memory: 22876kb
Test #58:
score: 0
Accepted
time: 156ms
memory: 23772kb
Test #59:
score: 0
Accepted
time: 3ms
memory: 7684kb
Test #60:
score: 0
Accepted
time: 1ms
memory: 12284kb
Test #61:
score: 0
Accepted
time: 5ms
memory: 9344kb
Test #62:
score: 0
Accepted
time: 3ms
memory: 9808kb