QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #187393 | #3005. Monotony | SolitaryDream# | AC ✓ | 2221ms | 12232kb | C++17 | 2.3kb | 2023-09-24 16:52:40 | 2023-09-24 16:52:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=21;
int n,m,a[N][N],go[N][N];
vector<int> st[N];
bool vis[N][N*N];
int f[N][N*N];
vector<int> ve[N*N];
int id[1<<N];
signed main()
{
scanf("%lld%lld",&n,&m);
// n=m=20;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
// a[i][j]=i*n+j;
scanf("%lld",&a[i][j]);
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
for(int k=0;k<m;k++)
if(a[i][k]<a[j][k])
go[i][j]|=1<<k;
int ans=0;
for(int S=1;S<(1<<m);S++)
{
int t=0;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(!id[go[i][j]&S])
id[go[i][j]&S]=++t;
for(int i=0;i<n;i++)
{
bool ok=1;
int la=-1,flag=-1;
for(int j=0;j<m;j++)
if(S>>j&1)
{
if(flag!=-1)
{
if(flag!=(la<a[i][j]))
ok=0;
}
if(la!=-1)
flag=(la<a[i][j]);
la=a[i][j];
}
if(!ok)
{
for(auto x:st[i])
vis[i][x]=0,f[i][x]=0;
st[i].clear();
continue;
}
for(int j=i+1;j<n;j++)
{
int p=id[go[i][j]&S];
ve[p].push_back(j);
f[j][p]++;
if(!vis[j][p])
vis[j][p]=1,st[j].push_back(p);
}
for(auto x:st[i])
{
ans+=f[i][x];
for(auto j:ve[x])
{
f[j][x]+=f[i][x];
if(!vis[j][x])
st[j].push_back(x),vis[j][x]=1;
}
vis[i][x]=0;
f[i][x]=0;
}
for(int j=i+1;j<n;j++)
ve[id[go[i][j]&S]].clear();
st[i].clear();
ans++;
}
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(id[go[i][j]&S])
id[go[i][j]&S]=0;
}
printf("%lld\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 100ms
memory: 4844kb
input:
13 17 155 221 29 114 165 175 120 107 27 134 125 116 11 56 100 20 15 88 128 38 111 198 212 173 136 44 164 64 150 83 19 93 197 194 219 25 16 50 2 55 151 34 163 76 217 209 141 174 80 144 159 60 156 54 149 97 28 102 145 26 35 188 160 65 152 135 6 21 8 62 195 70 127 30 171 205 147 177 210 117 10 103 161 ...
output:
40490
result:
ok answer is '40490'
Test #2:
score: 0
Accepted
time: 11ms
memory: 4104kb
input:
17 13 41 205 162 42 35 147 143 185 89 176 4 103 181 85 115 59 2 182 190 20 142 97 172 31 211 101 154 62 119 82 16 117 1 157 72 3 149 216 21 188 49 202 77 161 160 169 46 79 133 50 113 91 30 71 156 193 92 29 54 187 111 199 80 22 17 209 122 138 127 135 81 53 86 158 145 109 56 6 150 40 15 212 10 186 32 ...
output:
35799
result:
ok answer is '35799'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
1 2 1 2
output:
3
result:
ok answer is '3'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
1 2 2 1
output:
3
result:
ok answer is '3'
Test #6:
score: 0
Accepted
time: 69ms
memory: 3792kb
input:
1 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
output:
1048575
result:
ok answer is '1048575'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
2 1 1 2
output:
3
result:
ok answer is '3'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5900kb
input:
2 1 2 1
output:
3
result:
ok answer is '3'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
2 2 1 2 3 4
output:
9
result:
ok answer is '9'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
2 2 1 3 4 2
output:
9
result:
ok answer is '9'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
2 2 2 1 4 3
output:
9
result:
ok answer is '9'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
2 2 3 2 4 1
output:
9
result:
ok answer is '9'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
2 2 4 3 2 1
output:
9
result:
ok answer is '9'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
output:
225
result:
ok answer is '225'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
4 4 1 2 3 4 8 7 6 5 9 10 11 12 16 15 14 13
output:
225
result:
ok answer is '225'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
4 4 4 5 1 3 11 6 13 10 16 2 9 8 14 15 12 7
output:
110
result:
ok answer is '110'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
20 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
output:
1048575
result:
ok answer is '1048575'
Test #18:
score: 0
Accepted
time: 344ms
memory: 10096kb
input:
20 19 180 179 178 177 176 175 174 173 172 190 189 188 187 186 185 184 183 182 181 161 160 159 158 157 156 155 154 153 171 170 169 168 167 166 165 164 163 162 142 141 140 139 138 137 136 135 134 152 151 150 149 148 147 146 145 144 143 123 122 121 120 119 118 117 116 115 133 132 131 130 129 128 127 12...
output:
3485104
result:
ok answer is '3485104'
Test #19:
score: 0
Accepted
time: 338ms
memory: 8144kb
input:
20 19 9 8 7 6 5 4 3 2 1 19 18 17 16 15 14 13 12 11 10 28 27 26 25 24 23 22 21 20 38 37 36 35 34 33 32 31 30 29 47 46 45 44 43 42 41 40 39 57 56 55 54 53 52 51 50 49 48 66 65 64 63 62 61 60 59 58 76 75 74 73 72 71 70 69 68 67 85 84 83 82 81 80 79 78 77 95 94 93 92 91 90 89 88 87 86 104 103 102 101 10...
output:
1702885800
result:
ok answer is '1702885800'
Test #20:
score: 0
Accepted
time: 1048ms
memory: 8064kb
input:
20 19 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 13...
output:
1125119902
result:
ok answer is '1125119902'
Test #21:
score: 0
Accepted
time: 2221ms
memory: 12232kb
input:
20 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...
output:
1099509530625
result:
ok answer is '1099509530625'
Test #22:
score: 0
Accepted
time: 1692ms
memory: 10872kb
input:
20 20 56 358 43 382 339 146 206 335 390 285 57 35 252 147 378 106 352 395 129 214 308 166 167 359 207 244 77 181 148 158 227 34 200 125 342 93 122 95 377 228 79 26 268 253 192 84 70 301 384 231 171 198 126 137 237 185 310 242 246 153 115 168 203 346 96 399 306 32 215 138 176 360 303 101 275 332 177 ...
output:
153561
result:
ok answer is '153561'