QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#424713#7278. Brought Down the Grading Server?Lynkcat#0 161ms77512kbC++203.4kb2024-05-29 16:00:472024-05-29 16:00:48

Judging History

你现在查看的是最新测评结果

  • [2024-05-29 16:00:48]
  • 评测
  • 测评结果:0
  • 用时:161ms
  • 内存:77512kb
  • [2024-05-29 16:00:47]
  • 提交

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%