QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492592 | #165. Linear Gimmick | Afterlife# | AC ✓ | 8ms | 5084kb | C++20 | 1.5kb | 2024-07-26 14:14:56 | 2024-07-26 14:14:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1e3+7;
int n;
string s;
int cnt[N][2];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
cin>>s;
s=' '+s;
int ans=0;
for(int phase=0;phase<2;phase++)
{
memset(cnt,0,sizeof(cnt));
vector<int> pos[2];
for(int i=1;i<=n;i++)
{
pos[s[i]=='>'].push_back(i);
for(int j=0;j<2;j++)
cnt[i][j]=cnt[i-1][j];
cnt[i][s[i]=='>']++;
}
auto getpos=[&](vector<int> &v,int dir,int p)
{
if(dir>0)
{
auto x=lower_bound(v.begin(),v.end(),p)-v.begin();
return v[x+dir-1];
}
else
{
auto x=upper_bound(v.begin(),v.end(),p)-v.begin()-1;
return v[x+dir+1];
}
};
for(int i=1;i<=n;i++)//start
{
if(s[i]=='<')
{
int lc=cnt[i-1][1];
int rc=cnt[n][0]-cnt[i][0];
if(lc<=rc)
{
int p=getpos(pos[0],lc,i+1);
ans=max(ans,p);
}
else
{
int p=getpos(pos[1],-(rc+1),i-1);
ans=max(ans,n-p+1);
}
}
}
reverse(s.begin()+1,s.begin()+n+1);
for(int i=1;i<=n;i++)
s[i]^='<'^'>';
}
cout<<ans<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4404kb
input:
7 >><><<<
output:
7
result:
ok single line: '7'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4400kb
input:
5 >><<<
output:
5
result:
ok single line: '5'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4600kb
input:
6 ><<><<
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4536kb
input:
7 <<><<>>
output:
5
result:
ok single line: '5'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4316kb
input:
5 >>><>
output:
5
result:
ok single line: '5'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4308kb
input:
6 ><><><
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4336kb
input:
8 >>>><><<
output:
8
result:
ok single line: '8'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4320kb
input:
8 >>>>><>>
output:
8
result:
ok single line: '8'
Test #9:
score: 0
Accepted
time: 1ms
memory: 4316kb
input:
10 ><<><<<<<<
output:
10
result:
ok single line: '10'
Test #10:
score: 0
Accepted
time: 1ms
memory: 4544kb
input:
526 ><><<<>><><><<<<<>>>>>><><<>><<><<<><><>>><<<><><>>>>>>><<<><<>>><>><<><>><<><><><<>>><>>>>><<>>>><><><<<>><<<>><<><<><<<<>><<><>>><><<<><>>>><><<<<><>><<<<<<<><<<<<<>><><>><>>>>><>><>><<<<<><<><<<><<>>><>>><<<>>><>><<<>><><><<<>>><<<>><<><><<>><>><>><<<>>>><<<<<<><<<>>>>><<>><<><><>>><<><><><>>...
output:
526
result:
ok single line: '526'
Test #11:
score: 0
Accepted
time: 1ms
memory: 4308kb
input:
920 <<<<><>>><><><<<<><<<<>>><<>>>>>><<<>><><><>>>>><><<>><><<><<><><><<>>>>>>>><<<<<<>>>><<><<<<><><<>>><<>>>>><<<<>><<>><<><<><<>>><<<>>>>><<>><<><><<<><>>>><<>>>>>>>><<<><<><>>><>>>>>>><<<><>><<><<><<<><<><><>>>>><<><<><>>>>>><<<<<><><><<<<<<><>>>><<><<<><><<><<>>>><<><<<<<>><>>><<>>><>><<>>>><<<...
output:
917
result:
ok single line: '917'
Test #12:
score: 0
Accepted
time: 1ms
memory: 4576kb
input:
528 <>>>>>><><<>>>>>>>>>>><>><<<<>><<<<<><>><>><<>><>><>><<<<<>>><>>>>>>>>>>>><><<<<<>>><<<><><>><<<><<<<<><>><<>>><<<>>><<><<><><<>><><<<><><><>><>><><>>><<><><>><>><><><>><<>>>><><<><<<<><<><>>><<>>><>><<<<<<<>><<><><<>><>><><>><<<<<<<><><<<<>>><<>>><<<><<><>>><<<<>><<>>><><<<>><><>>>>>>>><<<>>>><...
output:
528
result:
ok single line: '528'
Test #13:
score: 0
Accepted
time: 1ms
memory: 4384kb
input:
837 <<<>><<<<><>><<<<<<>><<<<<<><<><>>><>>><<<>>>><>>><>><<><><>>><<><>>>>>>>><>>><<<<><>>>><>>>>>>>><<<>>><<<>>><>><<<<>>><>>>><<>><<>>><<<<<<<>><>><>><>><>><<<<><><<<>>>><<<><<<<><<<>>><>>>>>>>>><<>><<<<><><>><><<<<<>><<<>>>>>>><>><>>><<<>>><<>>><<<>>><>><>><><>><><<<>><>>><<>><<><<>>><><><<><><><...
output:
837
result:
ok single line: '837'
Test #14:
score: 0
Accepted
time: 1ms
memory: 4576kb
input:
761 >>>><><>>><<><>>>><<<>>>>>>>><>>><<>><>><<<<<>>>>>>>><<>><><<>><<<>><><>><><>>><<><>>><>><><<<>>><><><<<<>><>><<>>><<<>><<><<><<><>><>>><<>><<>><<<<>>>><><><>>>>><><>><><>><>>><<><<<<<<>><><>>><<<><>><<<>><<<><><<<<<><<<<<<><><<><<<<>><<<<><<<<><<><>>>>>>>><<>>>>>><<><>><<><><<>>>><><>><>>><>>><...
output:
761
result:
ok single line: '761'
Test #15:
score: 0
Accepted
time: 4ms
memory: 4704kb
input:
53592 <><<<<>>><>><<><><><<>><<<<<><><<<<>>><>>><><<<<>>>><>>>><<>>>>>><>><<<<<<><<<<>>><><><<><>>><><<><<>><<><<><><><<>>>><><><><<>>>><><<>><<<<><><<<<<<><<><>>><<><>>>><><<><><>><<<>><><>>><>><<><><><<<<><><><><<<<<>>>><<><<<<<>><><<<<>><<<<>>><><<<<<>><>><<>>><>><<<<<<<><<><<>>><<<<<>>>><>>>>>>>...
output:
53591
result:
ok single line: '53591'
Test #16:
score: 0
Accepted
time: 4ms
memory: 4788kb
input:
52256 >>><<><>><><<<>><<><>><>>><<>>><<<>>>><<<>><><><<<<<<<>>>><><<<<><<><<>><>>><><><><<><>>>><<>>><<<><<>>>>>><><<><>><>><><<<<<><<>><>>>>><<>><><<>><<<<>>>><<><><<><<<<<>>>>><>><>>>>><<><<>><>><<>><<<<<><<<><<<<><><<>>>>>>><><<<><><>>><>><<>>><<<<<<<>><<<><<<<<<>>><<<><<<<><><<>>>><<<><><<<<<>>>...
output:
52256
result:
ok single line: '52256'
Test #17:
score: 0
Accepted
time: 8ms
memory: 4764kb
input:
99234 >><>><<<<><<><<<<><><><><><<<>>><<><<><<<><<><><<<><<><>>><<<<><<<<>>>><<>>>><><><<><<<>><<<<<<<><<>><<><>>><><<>>>>><<<<<><><<<<<<<<<>><><><<><<<<<<><>>>><<<<<<<><><<<><><<<>><<>>>><<<<>>><>>>><><<>>>>><>><>>>><><<<<>><<>><<<>><><<<<<><<><<>><><<<<><<<<><<>>>><>><>><<<><<>><>>><<<<<>><<>>><<>...
output:
99234
result:
ok single line: '99234'
Test #18:
score: 0
Accepted
time: 3ms
memory: 5084kb
input:
90893 <<><><><<<<><>><<<<>>>><><><><<><<<>>><<<<>>>><<>>>><<<>>>><>><<<><<<<>><><><><><><<><><><><>>>><<>><>>>><<>>><<<<<<<<<><<>><<<>>>>>><><>><<<<>><<>><>><<><<<><<<<<<>><><><>>><>>>><<<<<><>>><>><<><>><<<<>>><>>><<>>><<>><<><<><><<<>><><<><<>><<<>><>><<>><><<>><<>>><><>>>><<>><>>><>><><>>>>>><<<>...
output:
90893
result:
ok single line: '90893'
Test #19:
score: 0
Accepted
time: 7ms
memory: 4816kb
input:
94064 >><><<>>><<>>>>>><>><<<><>><>>><<<>>>><><<>><><><<>><<><>><>><<>><<<<<<<>>><<<<<>>><><<<<<<>>><<>>>>><<>>><<<<>>>><>>><><>><<><<<<>><<><><>>><<<>>>>>><><<><<>><<<>>><>><<><><>><<<>>><>>><><>><>>><<<><>><><<<>><<<><<<>><<>><>>>><><<><>><<>>><>><>><>><<<>>>>>>><<><<<><<<<><>><<<><>><>>><><<<<<><...
output:
94064
result:
ok single line: '94064'
Test #20:
score: 0
Accepted
time: 3ms
memory: 4784kb
input:
85155 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
84901
result:
ok single line: '84901'
Test #21:
score: 0
Accepted
time: 8ms
memory: 4940kb
input:
97153 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
96645
result:
ok single line: '96645'
Test #22:
score: 0
Accepted
time: 8ms
memory: 4848kb
input:
99451 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
99140
result:
ok single line: '99140'
Test #23:
score: 0
Accepted
time: 2ms
memory: 4564kb
input:
56288 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<><><>>><<<>>>>><><<>>><><<<<><>><<<<><<<>><<<<>>>>>>><<<>><<<<>><<>>><<>>>><>><<><>>>>>>><><<>>>>>><>>><>><<>>><><><<><<<<<>>><><>>><<<>><<<><<>><><>>><><>>...
output:
56150
result:
ok single line: '56150'
Test #24:
score: 0
Accepted
time: 7ms
memory: 4840kb
input:
93160 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
92348
result:
ok single line: '92348'
Test #25:
score: 0
Accepted
time: 5ms
memory: 4804kb
input:
69172 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
53872
result:
ok single line: '53872'
Test #26:
score: 0
Accepted
time: 7ms
memory: 4836kb
input:
94056 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
89998
result:
ok single line: '89998'
Test #27:
score: 0
Accepted
time: 5ms
memory: 4588kb
input:
71927 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
58103
result:
ok single line: '58103'
Test #28:
score: 0
Accepted
time: 3ms
memory: 4612kb
input:
72348 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
70369
result:
ok single line: '70369'
Test #29:
score: 0
Accepted
time: 7ms
memory: 4788kb
input:
97095 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...
output:
93334
result:
ok single line: '93334'