QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#397998#3756. 字典序GraphcityAC ✓390ms19368kbC++201.0kb2024-04-24 21:04:512024-04-24 21:04:51

Judging History

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

  • [2024-04-24 21:04:51]
  • 评测
  • 测评结果:AC
  • 用时:390ms
  • 内存:19368kb
  • [2024-04-24 21:04:51]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e3;

int n,m,a[Maxn+5][Maxn+5],cnt[Maxn+5],vis[Maxn+5];
vector<int> v[Maxn+5];

inline void Clear()
{
    For(i,1,m) cnt[i]=vis[i]=0;
    For(i,1,n) vector<int>().swap(v[i]);
}
inline void Solve()
{
    For(i,1,n) For(j,1,m) cin>>a[i][j];
    For(j,1,m) For(i,1,n-1) if(a[i][j]>a[i+1][j])
        cnt[j]++,v[i].push_back(j);
    vector<int> ans; For(_,1,m)
    {
        int p=-1; For(i,1,m) if(!cnt[i] && !vis[i]) {p=i; break;}
        if(p==-1) {cout<<-1<<endl; Clear(); return;}
        vis[p]=1,ans.push_back(p);
        For(i,1,n-1) if(a[i][p]<a[i+1][p])
        {
            for(auto k:v[i]) cnt[k]--;
            vector<int>().swap(v[i]);
        }
    } for(auto i:ans) cout<<i<<' '; cout<<endl; Clear();
}

int main()
{
    // freopen("1.in","r",stdin);

    ios::sync_with_stdio(false);
    while(cin>>n>>m) Solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 390ms
memory: 19368kb

input:

8 3
6 1 2
3 2 2
7 2 2
7 2 2
7 2 2
9 2 2
10 2 2
4 10 2
6 2
3 1
3 4
3 4
3 7
3 7
3 8
7 7
1 3 3 2 6 3 3
1 3 3 2 6 3 3
1 3 3 2 6 3 3
6 3 3 2 1 4 3
6 3 3 2 4 4 3
7 2 4 2 4 10 6
7 3 4 10 4 3 3
4 3
2 3 9
2 4 9
2 4 9
2 4 9
8 10
9 6 6 3 6 10 1 8 2 5
9 6 6 3 6 10 1 9 2 5
5 3 8 6 7 2 1 7 2 10
5 10 8 7 4 7 1 4 8...

output:

2 1 3 
1 2 
1 2 3 4 5 6 7 
1 2 3 
7 3 1 2 4 5 6 8 9 10 
3 2 1 4 5 
1 3 2 4 5 6 7 8 9 
1 2 3 4 5 6 
1 2 3 4 5 6 
2 1 3 4 5 6 
6 4 3 5 1 2 7 8 9 10 
1 
2 1 
2 4 6 7 1 3 5 8 
1 2 
2 1 
1 2 3 
1 
9 4 3 5 1 2 6 7 8 10 
1 2 3 
1 
3 4 2 1 5 6 
1 3 4 5 6 7 2 8 9 
2 1 3 4 
1 2 3 4 6 5 
5 1 2 4 3 6 7 8 9 
1 2...

result:

ok 110618 tokens