QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#424713 | #7278. Brought Down the Grading Server? | Lynkcat# | 0 | 161ms | 77512kb | C++20 | 3.4kb | 2024-05-29 16:00:47 | 2024-05-29 16:00:48 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
// #define N
using namespace std;
const int N=500005;
int cnt;
poly G[N];
vector<poly>a,b;
int vis[N];
pa E[N];
int egt;
poly Rt[N],Lf[N];
int n,m,q;
int DFN;
int dfn[N];
int id[N];
int pl[N],pr[N];
int val[N];
int du[N];
int ct[N];
void dfs(int i)
{
while (G[i].size())
{
int u=G[i].back();G[i].pop_back();
if (vis[u]) continue;
vis[u]=1;
int v=E[u].fi^E[u].se^i;
dfs(v);
if (v==E[u].fi)
{
if (i!=cnt) Rt[v].push_back(i);
}
else if (v!=cnt) Lf[i].push_back(v);
}
}
void solve(int l,int r)
{
if (l==r) return;
int mid=l+(r-l)/2;
cnt=n;
++DFN;
egt=0;
for (int i=1;i<=n;i++)
{
pl[i]=l;
pr[i]=mid+1;
for (int j=l;j<=r;j++)
{
if (ct[a[i][j]])
{
b[i][pl[i]++]=a[i][j];
b[i][pr[i]++]=a[i][j];
}
ct[a[i][j]]^=1;
}
for (int j=l;j<=r;j++)
{
if (ct[a[i][j]])
{
if (dfn[a[i][j]]!=DFN)
{
dfn[a[i][j]]=DFN;
id[a[i][j]]=++cnt;
val[cnt]=a[i][j];
}
int u=id[a[i][j]];
++egt;
E[egt]=mp(i,u);
G[u].push_back(egt);
G[i].push_back(egt);
du[u]^=1,du[i]^=1;
ct[a[i][j]]=0;
}
}
// assert(sz(G[i])%2==0);
}
++cnt;
for (int i=1;i<cnt;i++)
if (du[i])
{
++egt;
E[egt]=mp(i,cnt);
G[cnt].push_back(egt),G[i].push_back(egt);
du[i]=0;
}
for (int i=1;i<=cnt;i++)
{
dfs(i);
}
for (int i=1;i<=n;i++)
{
// if (sz(Lf[i])!=sz(Rt[i]))
// {
// cout<<i<<" "<<pl[i]-l<<" "<<pr[i]-mid-1<<'\n';
// cout<<sz(Lf[i])<<" "<<sz(Rt[i])<<endl;
// }
for (auto u:Lf[i]) b[i][pl[i]++]=val[u];
for (auto u:Rt[i]) b[i][pr[i]++]=val[u];
// assert(sz(Lf[i])==sz(Rt[i]));
poly().swap(Lf[i]);
poly().swap(Rt[i]);
}
for (int i=1;i<=egt;i++) vis[i]=0;
for (int i=1;i<=cnt;i++) poly().swap(G[i]);
for (int i=1;i<=n;i++)
for (int j=l;j<=r;j++)
a[i][j]=b[i][j];
solve(l,mid);
solve(mid+1,r);
}
mt19937_64 rnd(time(0));
void BellaKira()
{
cin>>n>>m>>q;
a=vector<poly>(n+1,poly(m+1,0));
b=a;
for (int i=1;i<=n;i++)
for (int j=0;j<m;j++)
{
// cin>>a[i][j];
a[i][j]=rnd()%q+1;
}
solve(0,m-1);
for (int i=1;i<=n;i++)
{
for (int j=0;j<m;j++)
{
cout<<a[i][j]<<" ";
}
cout<<'\n';
}
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 7888kb
input:
3 2 3 1 2 2 3 2 3
output:
3 1 1 3 3 2
result:
wrong answer
Subtask #2:
score: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 161ms
memory: 77512kb
input:
100000 2 100000 70318 14894 32116 90327 63866 29061 53683 63612 70370 78264 42647 76881 39251 31741 61186 66491 57686 65819 53278 59145 71962 26052 81040 55279 50859 51310 46800 24546 85013 91165 61530 21890 84003 29099 33573 86182 49212 10639 91851 97312 57682 14067 5243 69674 99007 62508 26290 555...
output:
72198 2182 72354 13700 48906 91941 89372 84666 30904 92878 1582 87706 65906 41500 30723 12804 24895 55219 5740 80871 52000 77372 41112 46927 88025 98167 66764 66683 34667 12914 81300 62163 30749 44896 12192 97512 37703 75971 78869 54373 23175 83803 33237 58064 14553 52457 8396...
result:
wrong answer
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Wrong Answer
Test #56:
score: 0
Wrong Answer
time: 3ms
memory: 8020kb
input:
3 4 3 2 3 2 2 2 3 3 2 2 2 3 2
output:
3 1 3 1 2 3 2 2 1 2 1 3
result:
wrong answer
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #2:
0%
Subtask #9:
score: 0
Skipped
Dependency #3:
0%
Subtask #10:
score: 0
Skipped
Dependency #1:
0%