제출 #800117

#제출 시각아이디문제언어결과실행 시간메모리
800117lollipop카니발 티켓 (IOI20_tickets)C++17
41 / 100
484 ms75300 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define ll long long #define pb push_back #define s second #define f first #define pf push_front #define inf 100000000000000000 #define bitebi __builtin_popcountll #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ ) #define YES cout <<"YES\n" #define NO cout << "NO\n" #define debug cout << "Here Fine" << endl ; #define pr pair < int , int > #define fbo find_by_order // returns iterator #define ook order_of_key // returns strictly less numbers than key using namespace std ; //#pragma GCC optimize("Ofast") //#pragma GCC target("avx,avx2,fma") using namespace __gnu_pbds; using namespace __gnu_cxx; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> const double Pi=acos(-1.0); const double EPS=1E-8; const int mod = 1000000007 ; const int mod1 = 998244353 ; const int NN = 2e5 + 10 ; mt19937 R(time(0)); map < int , int > ma , ma1 ; #include "tickets.h" // static int n; // static int m; // static int k; // static std::vector<std::vector<int>> d; // static std::vector<std::vector<int>> x; // static int called = 0; // static void check(bool cond, std::string message) { // if (!cond) { // printf("WA\n"); // printf("%s\n", message.c_str()); // exit(0); // } // } // void allocate_tickets( std::vector<std::vector<int>> _d) { // check(!called, "allocate_tickets called more than once"); // d = _d; // check((int)d.size() == n, "allocate_tickets called with parameter of wrong size"); // for (int i = 0; i < n; i++) { // check((int)d[i].size() == m, "allocate_tickets called with parameter of wrong size"); // } // called = 1; // } vector < int > v[ 2000 ][ 2 ] ; long long find_maximum(int k, std::vector<std::vector<int>> d){ vector<std::vector<int>> pas ; if( k == 1 && d[ 0 ].size() == 1 ){ FOR( i , d.size() ){ vector < int > pas1 ; FOR( j , d[ i ].size() ) pas1.pb( 0 ) ; pas.pb( pas1 ) ; } ll ans = 0 ; vector < int > v ; for( auto x : d ) v.pb( x[ 0 ] ) ; sort( v.begin() , v.end() ) ; for( int j = 0 ; j < v.size() / 2 ; j ++ ) ans = ans + v[ v.size() - j - 1 ] - v[ j ] ; allocate_tickets( pas ) ; return ans ; } // fill with -1 and find the max/min pairs if( k == 1 ){ int n = d.size() ; pair < int , int > p[ n ] ; FOR( i , d.size() ){ vector < int > pas1 ; vector < pair < int , int > > vv ; FOR( j , d[ i ].size() ){ pas1.pb( -1 ) ; vv.pb( { d[ i ][ j ] , j } ) ; } sort( vv.begin() , vv.end() ) ; p[ i ].f = vv[ 0 ].s ; p[ i ].s = vv[ vv.size() - 1 ].s ; pas.pb( pas1 ) ; } vector < pair < int , int > > cur ; FOR( i , n ){ cur.pb( { d[ i ][ p[ i ].f ] + d[ i ][ p[ i ].s ] , i } ) ; } sort( cur.begin() , cur.end() ) ; ll ans = 0 ; FOR( i , n / 2 ){ int pos = cur[ i ].s ; pas[ pos ][ p[ pos ].f ] = 0 ; ans -= d[ pos ][ p[ pos ].f ] ; } for( int i = n / 2 ; i < n ; i ++ ){ int pos = cur[ i ].s ; pas[ pos ][ p[ pos ].s ] = 0 ; ans += d[ pos ][ p[ pos ].s ] ; } allocate_tickets( pas ) ; return ans ; } FOR( i , d.size() ){ vector < int > pas1 ; FOR( j , d[ i ].size() ) pas1.pb( -1 ) ; FOR( j , d[ i ].size() ){ v[ i ][ d[ i ][ j ] ].pb( j ) ; } pas.pb( pas1 ) ; } ll ans = 0 ; int n = d.size() ; int col = 0 ; while( k -- ){ priority_queue < pair < int , int > > qu ; int been[ n ] ; FOR( i , n ) been[ i ] = 0 ; int cc1 = 0 , cc2 = 0 ; FOR( i , n ) qu.push( { v[ i ][ 0 ].size() , i } ) ; while( true ){ if( qu.size() == 0 ) break ; pair < int , int > p ; p = qu.top() ; if( cc1 >= n / 2 && v[ p.s ][ 1 ].size() != 0 ) break ; if( v[ p.s ][ 0 ].size() == 0 ) break ; cc1 ++ ; int x = v[ p.s ][ 0 ][ v[ p.s ][ 0 ].size() - 1 ] ; been[ p.s ] = 1 ; v[ p.s ][ 0 ].pop_back() ; pas[ p.s ][ x ] = col ; qu.pop() ; } FOR( i , n ){ if( been[ i ] == 1 ) continue ; cc2 ++ ; int x = v[ i ][ 1 ][ v[ i ][ 1 ].size() - 1 ] ; v[ i ][ 1 ].pop_back() ; pas[ i ][ x ] = col ; } ans = ans + min( cc1 , cc2 ) ; col ++ ; } allocate_tickets( pas ) ; return ans ; } // int main() { // assert(scanf("%d %d %d", &n, &m, &k) == 3); // x.resize(n); // for (int i = 0; i < n; i++) { // x[i].resize(m); // for (int j=0; j < m; j++) { // assert(scanf("%d", &x[i][j]) == 1); // } // } // fclose(stdin); // long long answer = find_maximum(k, x); // check(called, "failure to call allocate_tickets"); // printf("OK\n"); // printf("%lld\n", answer); // for (int i = 0; i < n; i++) { // for (int j = 0; j < m; j++) { // if (j) printf(" "); // printf("%d", d[i][j]); // } // printf("\n"); // } // fclose(stdout); // return 0; // }

컴파일 시 표준 에러 (stderr) 메시지

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
   66 |      FOR( i , d.size() ){
      |           ~~~~~~~~~~~~                   
tickets.cpp:66:6: note: in expansion of macro 'FOR'
   66 |      FOR( i , d.size() ){
      |      ^~~
tickets.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
   68 |         FOR( j , d[ i ].size() ) pas1.pb( 0 ) ;
      |              ~~~~~~~~~~~~~~~~~           
tickets.cpp:68:9: note: in expansion of macro 'FOR'
   68 |         FOR( j , d[ i ].size() ) pas1.pb( 0 ) ;
      |         ^~~
tickets.cpp:75:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |      for( int j = 0 ; j < v.size() / 2 ; j ++ ) ans = ans + v[ v.size() - j - 1 ] - v[ j ] ;
      |                       ~~^~~~~~~~~~~~~~
tickets.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
   84 |        FOR( i , d.size() ){
      |             ~~~~~~~~~~~~                 
tickets.cpp:84:8: note: in expansion of macro 'FOR'
   84 |        FOR( i , d.size() ){
      |        ^~~
tickets.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
   87 |         FOR( j , d[ i ].size() ){
      |              ~~~~~~~~~~~~~~~~~           
tickets.cpp:87:9: note: in expansion of macro 'FOR'
   87 |         FOR( j , d[ i ].size() ){
      |         ^~~
tickets.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  116 |     FOR( i , d.size() ){
      |          ~~~~~~~~~~~~                    
tickets.cpp:116:5: note: in expansion of macro 'FOR'
  116 |     FOR( i , d.size() ){
      |     ^~~
tickets.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  118 |         FOR( j , d[ i ].size() ) pas1.pb( -1 ) ;
      |              ~~~~~~~~~~~~~~~~~           
tickets.cpp:118:9: note: in expansion of macro 'FOR'
  118 |         FOR( j , d[ i ].size() ) pas1.pb( -1 ) ;
      |         ^~~
tickets.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  119 |         FOR( j , d[ i ].size() ){
      |              ~~~~~~~~~~~~~~~~~           
tickets.cpp:119:9: note: in expansion of macro 'FOR'
  119 |         FOR( j , d[ i ].size() ){
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...