QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #480369 | #8364. permutation | QZJ123456 | Compile Error | / | / | C++14 | 6.6kb | 2024-07-16 14:53:32 | 2024-07-16 14:53:33 |
Judging History
answer
#include <cstdio>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,popcnt,tune=native")
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define NEGATIVE
struct freader {
FILE *f;
# ifdef ONLINE_JUDGE
char buf[1048577], *p1, *p2;
# define fgetc(f) (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1048576, f), p1 == p2) ? EOF : *p1++)
# endif
# ifdef BOOLTRANS
bool neof;
# define NEOF(c) ((c) != EOF || (neof = 0))
# else
# define NEOF(c) ((c) != EOF)
# endif
freader(FILE *_f = stdin) : f(_f) {
# ifdef BOOLTRANS
neof = 1;
# endif
# ifdef ONLINE_JUDGE
setvbuf(f, NULL, _IONBF, 0);
p1 = p2 = buf;
# endif
}
void read(char &x) {
for (x = fgetc(f); NEOF(x) && x <= ' '; x = fgetc(f));
return;
}
void read(char *s) {
for (*s = fgetc(f); NEOF(*s) && *s <= ' '; *s = fgetc(f));
for (s++; NEOF(*s = fgetc(f)) && *s > ' '; s++);
*s = '\0';
return;
}
void read(float x) {return fputs("Error: Unable to read float.", stderr), void();}
void read(double x) {return fputs("Error: Unable to read double.", stderr), void();}
void read(long double x) {return fputs("Error: Unable to read long double.", stderr), void();}
template<typename T> void read(T &x) {
char c(fgetc(f));
# ifdef NEGATIVE
for (; NEOF(c) && (c < '0' || c > '9') && c != '-'; c = fgetc(f));
if (c == '-')
for (c = fgetc(f), x = 0; NEOF(c) && c >= '0' && c <= '9'; c = fgetc(f)) x = (x << 3) + (x << 1) - (c ^ '0');
else
for (x = 0; NEOF(c) && c >= '0' && c <= '9'; c = fgetc(f)) x = (x << 3) + (x << 1) + (c ^ '0');
# else
for (; NEOF(c) && (c < '0' || c > '9'); c = fgetc(f));
for (x = 0; NEOF(c) && c >= '0' && c <= '9'; c = fgetc(f)) x = (x << 3) + (x << 1) + (c ^ '0');
# endif
return;
}
# if __cplusplus >= 201103
template<typename T, typename...Args> void read(T &x, Args &...args) {return read(x), read(args...);}
# endif
template<typename T> freader &operator >> (T &x) {
# ifdef BOOLTRANS
return *this ? read(x), *this : *this;
# else
return read(x), *this;
# endif
}
# ifdef BOOLTRANS
operator bool() {return neof;}
# endif
# ifdef ONLINE_JUDGE
# undef fgetc
# endif
# undef NEOF
} fin;
struct fwriter {
FILE *f;
# ifdef ONLINE_JUDGE
char buf[1048577], *p1;
# define fputc(c, f) (p1 == buf + 1048576 ? fwrite(buf, 1, 1048576, f), *(p1 = buf)++ = (c) : *p1++ = (c))
# endif
fwriter(FILE *_f = stdout): f(_f) {
# ifdef ONLINE_JUDGE
setvbuf(f, NULL, _IONBF, 0);
p1 = buf;
# endif
}
~fwriter() {flush();}
void flush() {
# ifdef ONLINE_JUDGE
fwrite(buf, 1, p1 - buf, f), p1 = buf;
# else
fflush(f);
# endif
return;
}
void write(char c) {return fputc(c, f), void();}
void write(char *s) {
for (; *s; s++) fputc(*s, f);
return;
}
void write(const char *s) {
for (; *s; s++) fputc(*s, f);
return;
}
void write(float x) {return fputs("Error: Unable to write float.", stderr), void();}
void write(double x) {return fputs("Error: Unable to write double.", stderr), void();}
void write(long double x) {return fputs("Error: Unable to write long double.", stderr), void();}
template<typename T> void write(T x) {
if (!x) return fputc('0', f), void();
if (x < 0) fputc('-', f), x = -x;
char s[41];
int l(0);
while (x) s[l++] = x % 10 ^ '0', x /= 10;
while (l--) fputc(s[l], f);
return;
}
# if __cplusplus >= 201103
template<typename T, typename...Args> void write(T x, Args...args) {return write(x), write(args...);}
# endif
template<typename T> fwriter &operator << (T x) {return write(x), *this;}
# ifdef ONLINE_JUDGE
# undef fputc
# endif
} fout;
int a[15],n,m,tot,nid[300005];
bool mark[15];
const int mod=1e7+19;
struct hashtable{
int cnt,head[mod],nxt[mod],id[mod];
ll val[mod];
void ins(ll x,int i){
int now=head[x%mod];
while(now&&val[now]!=x)now=nxt[now];
if(now==0)val[++cnt]=x,id[cnt]=i,nxt[cnt]=head[x%mod],head[x%mod]=cnt;
else id[now]=i;
}
int Get(ll x){
int now=head[x%mod];
while(now&&val[now]!=x)now=nxt[now];
if(now==0)return -1;
return id[now];
}
}hs;
int Getid(ll h){
int tmp=hs.Get(h);
if(tmp!=-1)return tmp;
hs.ins(h,++tot);
return tot;
}
ll pw[15];
vector<int>vec[365005];
int d[365005],d1[365005];
void dfs(int now){
if(now==n+1){
ll h=0;
for(int i=1;i<=n;i++)h=h*10+a[i];
// cout<<h<<endl;
int cur=Getid(h);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i]<=a[j])continue;
ll h1=h-(a[i]-a[j])*pw[n-i]-(a[j]-a[i])*pw[n-j];
// cout<<h<<" "<<h1<<" "<<i<<" "<<j<<endl;
int to=Getid(h1);
vec[cur].push_back(to);
d[to]++,d1[to]++;
}
}
return;
}
for(int i=1;i<=n;i++){
if(!mark[i]){
a[now]=i;
mark[i]=1;
dfs(now+1);
mark[i]=0;
}
}
}
int que[365005],hd=1,tl;
bitset<2005>bs1[365005];
bitset<60005>bs2[41005];
int ans[50005];
int main(){
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
scanf("%d%d",&n,&m);
pw[0]=1;
for(int i=1;i<=n;i++)pw[i]=pw[i-1]*10;
dfs(1);
if(m<=2000){
for(int i=1;i<=m;i++){
ll tmp=0;
for(int j=1;j<=n;j++)fin.read(a[j]),tmp=tmp*10+a[j];
nid[i]=Getid(tmp);
bs1[nid[i]][i]=1;
}
for(int i=1;i<=tot;i++){
if(!d[i])que[++tl]=i;
}
while(hd<=tl){
int top=que[hd++];
for(auto to:vec[top]){
d[to]--;
bs1[to]|=bs1[top];
if(!d[to])que[++tl]=to;
}
}
for(int i=1;i<=m;i++)cout<<bs1[nid[i]].count()<<endl;
return 0;
}
// cout<<111;
for(int i=1;i<=m;i++){
ll tmp=0;
for(int j=1;j<=n;j++)fin.read(a[j]),tmp=tmp*10+a[j];
nid[i]=Getid(tmp);
}
int s=6e4;
for(int i=1;i<=(m-1)/s+1;i++){
int L=(i-1)*s+1,R=min(i*s,m);
// cout<<L<<" "<<R<<endl;
for(int j=1;j<=tot;j++)bs2[j].reset();
for(int j=L;j<=R;j++){
bs2[nid[j]][j-L+1]=1;
}
hd=1,tl=0;
for(int j=1;j<=tot;j++){
d[j]=d1[j];
if(!d[j])que[++tl]=j;
}
while(hd<=tl){
int top=que[hd++];
for(auto to:vec[top]){
d[to]--;
bs2[to]|=bs2[top];
if(!d[to])que[++tl]=to;
}
}
for(int j=1;j<=tot;j++)ans[j]+=bs2[j].count();
}
for(int i=1;i<=m;i++)fout.write(ans[nid[i]],'\n');
return 0;
}
Details
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/gthr.h:148,
from /usr/include/c++/13/ext/atomicity.h:35,
from /usr/include/c++/13/bits/ios_base.h:39,
from /usr/include/c++/13/streambuf:43,
from /usr/include/c++/13/bits/streambuf_iterator.h:35,
from /usr/include/c++/13/iterator:66,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54,
from answer.code:4:
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:121:1: error: attribute value ‘t...