QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #358506 | #6822. Bracket Query | crsfaa | WA | 11ms | 3856kb | C++14 | 2.0kb | 2024-03-19 20:24:16 | 2024-03-19 20:24:16 |
Judging History
answer
#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
struct node
{
int v,w;
};
vector<node> a[3005];
queue<int> q;
int d[3005],cnt[3005];
bool t[3005];
void spfa(int n)
{
memset(d,127/3,sizeof(d));
memset(t,0,sizeof(t));
memset(cnt,0,sizeof(cnt));
d[n]=0,t[n]=1;
int u,v,w,i;
q.push(n);
while(q.size())
{
u=q.front();
t[u]=0;
q.pop();
for(i=0;i<a[u].size();i++)
{
v=a[u][i].v,w=a[u][i].w;
if(d[u]+w<d[v])
{
d[v]=d[u]+w;
cnt[v]=cnt[u]+1;
if(cnt[v]>=n+2)
{
cout<<"?";
exit(0);
}
if(!t[v])
t[v]=1,q.push(v);
}
}
}
}
void add(int x,int y,int c)//sx-sy<=c
{
// cout<<x<<'-'<<y<<"<="<<c<<endl;
a[y].push_back({x,c});
}
/*
s0,s2... 2x,x>=0
s1,s3... 2x+1,x>=0
s0=sn=0
*/
int main()
{
int n=read(),q=read(),i;
for(i=0;i<=n;i++)
add(n+1,i,0);
add(0,n+1,0),add(n,n+1,0);
for(i=1;i<=n;i++)
if(i%2==0)
{
//i-1:2x+1 i:2x
//s[i]-1<=s[i-1]<=s[i]
add(i,i-1,1),add(i-1,i,0);
}
else
{
//i-1:2x i:2x+1
//s[i]<=s[i-1]<=s[i]+1
add(i,i-1,0),add(i-1,i,1);
}
for(i=0;i<=n+1;i++)
a[n+2].push_back({i,0});
while(q--)
{
int l=read(),r=read(),c=read();
//s[r]-s[l-1]=c
if((c+114514)%2!=(r-l+1)%2)
{
cout<<"?";
exit(0);
}
if(l%2==r%2)
{
//2s[r]-2s[l-1]=c
add(l-1,r,-c/2),add(r,l-1,c/2);
}
else if(r%2)
{
//2s[r]+1-2s[l-1]=c
add(l-1,r,-(c-1)/2),add(r,l-1,(c-1)/2);
}
else
{
//2s[r]-2s[l-1]-1=c
add(l-1,r,-(c+1)/2),add(r,l-1,(c+1)/2);
}
}
spfa(n+2);
int mn=2e9;
for(i=0;i<=n+1;i++)
mn=min(mn,d[i]);
for(i=0;i<=n;i++)
d[i]-=mn,d[i]=d[i]*2+i%2;
cout<<"! ";
for(i=1;i<=n;i++)
putchar(d[i]>d[i-1]?'(':')');
}
/*
4 1
1 2 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3664kb
input:
4 1 1 2 0
output:
! ()()
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
4 1 1 2 2
output:
! (())
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
2 2 1 1 1 2 2 -1
output:
! ()
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
2 1 1 1 2
output:
?
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
4 0
output:
! ()()
result:
ok ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
8 2 1 5 1 3 7 1
output:
! ()()()()
result:
ok ok
Test #7:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
3000 0
output:
! ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()...
result:
ok ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
2 1 1 2 2
output:
?
result:
ok ok
Test #9:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
3000 1 1 3000 0
output:
! ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()...
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
8 2 1 6 2 3 7 1
output:
! ()((()))
result:
ok ok
Test #11:
score: 0
Accepted
time: 11ms
memory: 3828kb
input:
3000 3 1111 1113 3 1112 1114 -1 1113 1115 3
output:
?
result:
ok ok
Test #12:
score: -100
Wrong Answer
time: 0ms
memory: 3728kb
input:
2 1 1 2 -2
output:
! ()
result:
wrong answer requirement not satisified