QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #400279 | #7942. $K$ Subsequences | ucup-team3160 | Compile Error | / | / | C++14 | 5.2kb | 2024-04-27 09:22:03 | 2024-04-27 09:22:05 |
Judging History
answer
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
# include <bits/stdc++.h>
using namespace std ;
int n , m ;
int a[200005] ;
typedef pair< int , int > pii ;
int cnt1 = 0 , cnt2 = 0 ;
int Read()
{
int num=0,k=1; //k是正负数标记
char c=getchar();
while(c!='-'&&(c<'0'||c>'9')) c=getchar();//注意判断'-'
if(c=='-')
{
k=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
num=(num<<3)+(num<<1)+(c^48);//num<<3相当于num*8,num<<1相当于num*2,
c=getchar(); //c^48利用位运算优化，相当于c-'0' ,但是一定要加括号
}
return num*k;
}
void print1(int x)
{
if(x>9) print1(x/10); //把这个数一位一位的输出
putchar(x%10+'0');
}
struct pq1
{
priority_queue < pii > q1 , q2 ;
priority_queue < pii , vector < pii > , greater < pii > > q3 , q4 ;
void init()
{
while ( q1.size() ) q1.pop() ;
while ( q2.size() ) q2.pop() ;
while ( q3.size() ) q3.pop() ;
while ( q4.size() ) q4.pop() ;
}
void push( pii x )
{
// printf("push:{%d,%d}\n" , x.first , x.second) ;
q1.push( x ) ;
q3.push( x ) ;
}
void del( pii x )
{
// printf("pop:{%d,%d}\n" , x.first , x.second) ;
q2.push( x ) ;
q4.push( x ) ;
}
pii maxv()
{
while ( q1.size() && q2.size() )
{
if ( q1.top() != q2.top() ) return q1.top() ;
q1.pop() , q2.pop() ;
}
return q1.top() ;
}
pii minv()
{
// puts("qmin:") ;
while ( q3.size() && q4.size() )
{
// printf("{%d,%d} {%d,%d}\n" , q3.top().first , q3.top().second , q4.top().first , q4.top().second) ;
if ( q3.top() != q4.top() ) return q3.top() ;
q3.pop() , q4.pop() ;
}
// printf("{%d,%d}\n" , q3.top().first , q3.top().second) ;
return q3.top() ;
}
} q ;
bool check( int v )
{
// printf("check:%d\n" , v) ;
q.init() ;
for ( int i = 1 ; i <= m ; i++ ) q.push( { 0 , i } ) ;
for ( int i = 1 ; i <= n ; i++ )
{
if ( a[i] == 1 )
{
auto now = q.minv() ;
// printf("now:%d %d\n" , now.first , now.second) ;
q.del( now ) ;
if ( now.first + 1 > v ) return false ;
q.push( { now.first + 1 , now.second } ) ;
}
else
{
auto now = q.maxv() ;
if ( now.first == 0 ) continue ;
q.del( now ) ;
q.push( { now.first - 1 , now.second } ) ;
}
}
return true ;
}
int ans[200005] ;
void solve()
{
scanf("%d%d" , &n , &m) ;
for ( int i = 1 ; i <= n ; i++ ) a[i] = Read() ;
int l = 0 , r = n ;
while ( l < r )
{
int mid = ( l + r ) >> 1 ;
if ( check( mid ) ) r = mid ;
else l = mid + 1 ;
}
q.init() ;
for ( int i = 1 ; i <= m ; i++ ) q.push( { 0 , i } ) ;
for ( int i = 1 ; i <= n ; i++ )
{
if ( a[i] == 1 )
{
auto now = q.minv() ;
// printf("now:%d %d\n" , now.first , now.second) ;
q.del( now ) ;
print1( now.second ) ;
putchar(' ') ;
// printf("%d " , now.second) ;
q.push( { now.first + 1 , now.second } ) ;
}
else
{
auto now = q.maxv() ;
print1( now.second ) ;
putchar(' ') ;
// printf("%d " , now.second) ;
if ( now.first == 0 ) continue ;
q.del( now ) ;
q.push( { now.first - 1 , now.second } ) ;
}
}
// printf("%d\n" , l) ;
puts("") ;
}
int main()
{
// freopen("1.in" , "r" , stdin) ;
// freopen("1.out" , "w" , stdout) ;
int t ;
scanf("%d" , &t) ;
while ( t -- ) solve() ;
// printf("%d %d\n" , cnt1 , cnt2) ;
return 0 ;
}
Details
answer.code:22:39: warning: bad option ‘-fwhole-program’ to pragma ‘optimize’ [-Wpragmas]
22 | #pragma GCC optimize("-fwhole-program")
| ^
answer.code:29:41: warning: bad option ‘-fstrict-overflow’ to pragma ‘optimize’ [-Wpragmas]
29 | #pragma GCC optimize("-fstrict-overflow")
| ^
answer.code:31:41: warning: bad option ‘-fcse-skip-blocks’ to pragma ‘optimize’ [-Wpragmas]
31 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
answer.code:45:51: warning: bad option ‘-funsafe-loop-optimizations’ to pragma ‘optimize’ [-Wpragmas]
45 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
answer.code:56:10: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
56 | int Read()
| ^
answer.code:56:10: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:56:10: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:56:10: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:74:18: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
74 | void print1(int x)
| ^
answer.code:74:18: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:74:18: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:74:18: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:83:19: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
83 | void init()
| ^
answer.code:83:19: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:83:19: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:83:19: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:90:26: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
90 | void push( pii x )
| ^
answer.code:90:26: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:90:26: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:90:26: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:96:25: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
96 | void del( pii x )
| ^
answer.code:96:25: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:96:25: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:96:25: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:102:18: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
102 | pii maxv()
| ^
answer.code:102:18: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:102:18: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:102:18: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:111:18: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
111 | pii minv()
| ^
answer.code:111:18: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:111:18: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:111:18: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:124:19: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
124 | bool check( int v )
| ^
answer.code:124:19: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:124:19: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:124:19: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:150:12: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
150 | void solve()
| ^
answer.code:150:12: warning: bad option ‘-fstrict-overflow’ to attribute ‘optimize’ [-Wattributes]
answer.code:150:12: warning: bad option ‘-fcse-skip-blocks’ to attribute ‘optimize’ [-Wattributes]
answer.code:150:12: warning: bad option ‘-funsafe-loop-optimizations’ to attribute ‘optimize’ [-Wattributes]
answer.code:190:10: warning: bad option ‘-fwhole-program’ to attribute ‘optimize’ [-Wattributes]
1...