QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#397998 | #3756. 字典序 | Graphcity | AC ✓ | 390ms | 19368kb | C++20 | 1.0kb | 2024-04-24 21:04:51 | 2024-04-24 21:04:51 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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