제출 #408698

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
408698		mat_v	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	881 ms	102712 KiB

tickets

#include "tickets.h"

#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define pii pair<int,int>
#define xx first
#define yy second
#define pb push_back


using namespace std;
typedef long long ll;

pii mat[1505][1505];
int ans[1505][1505];
int kol[1505];
int dole[1505];
int ima[1505];
bool uzo[1505];

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	ff(i,0,n - 1){
        ff(j,0,m - 1){
            mat[i + 1][j + 1] = {x[i][j], j+1};
        }
	}
	ff(i,1,n)sort(mat[i] + 1, mat[i] + m + 1);
//	ff(i,1,n){
//        ff(j,1,m){
//            cout << mat[i][j].xx << mat[i][j].yy << " ";
//        }
//        cout << "\n";
//	}
//	cout << "\n";
    ff(i,1,n)ff(j,1,m)ans[i][j] = -1;

    ll suma = 0;
    ff(i,1,n){
        ff(j,1,k)suma -= mat[i][j].xx;
    }

    priority_queue<pii> pq;
    ff(i,1,n){
        pq.push({mat[i][m].xx + mat[i][k].xx, i});
    }
    ff(i,1,(n*k)/2){
        pii sta = pq.top();
        pq.pop();
        kol[sta.yy]++;
        suma += sta.xx;
        if(kol[sta.yy] < k){
            pq.push({mat[sta.yy][k-kol[sta.yy]].xx + mat[sta.yy][m-kol[sta.yy]].xx, sta.yy});
        }
    }
    int r = 0;
    ff(i,1,n){
        dole[i] = k - kol[i];
        assert(kol[i] <= k);
        r += kol[i];
    }
    assert(r == (n*k)/2);

    ff(j,1,k){

        int tr = 0;
        ff(i,1,n)uzo[i] = 0;
        ff(i,1,n){
            if(dole[i] == 0){
                uzo[i] = 1;
                tr++;
            }
        }
        ff(i,1,n){
            if(uzo[i])continue;
            if(tr == n/2)break;
            if(kol[i] > 0){
                tr++;
                uzo[i] = 1;
            }
        }
        ff(i,1,n){
            if(uzo[i]){
                ans[i][m - kol[i] + 1] = j-1;
                kol[i]--;
            }
            else{
                ans[i][dole[i]] = j-1;
                dole[i]--;
            }
        }
    }

//    ff(i,1,n){
//        //cout << kol[i] << "\n";
//        assert(kol[i] <= k);
//        int dole = k - kol[i];
//        ff(j,1,k){
//            if(ima[j] < n/2){
//                if(kol[i] > 0){
//                    ans[i][mat[i][m-kol[i]+1].yy] = j-1;
//                    kol[i]--;
//                    ima[j]++;
//                }
//                else{
//                    ans[i][mat[i][dole].yy] = j-1;
//                    dole--;
//                }
//            }
//            else{
//                ans[i][mat[i][dole].yy] = j-1;
//                dole--;
//            }
//        }
//    }
    vector<vector<int>>answer;
    ff(i,1,n){
        vector<int> row;
        ff(j,1,m)row.pb(ans[i][j]);
        answer.pb(row);
    }

	allocate_tickets(answer);
	return suma;
}
/*
2 3 2
0 2 5
1 1 3

*/

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

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:25:2: note: in expansion of macro 'ff'
   25 |  ff(i,0,n - 1){
      |  ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:26:9: note: in expansion of macro 'ff'
   26 |         ff(j,0,m - 1){
      |         ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:30:2: note: in expansion of macro 'ff'
   30 |  ff(i,1,n)sort(mat[i] + 1, mat[i] + m + 1);
      |  ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:38:5: note: in expansion of macro 'ff'
   38 |     ff(i,1,n)ff(j,1,m)ans[i][j] = -1;
      |     ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:38:14: note: in expansion of macro 'ff'
   38 |     ff(i,1,n)ff(j,1,m)ans[i][j] = -1;
      |              ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:41:5: note: in expansion of macro 'ff'
   41 |     ff(i,1,n){
      |     ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:42:9: note: in expansion of macro 'ff'
   42 |         ff(j,1,k)suma -= mat[i][j].xx;
      |         ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:46:5: note: in expansion of macro 'ff'
   46 |     ff(i,1,n){
      |     ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:49:5: note: in expansion of macro 'ff'
   49 |     ff(i,1,(n*k)/2){
      |     ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:59:5: note: in expansion of macro 'ff'
   59 |     ff(i,1,n){
      |     ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:66:5: note: in expansion of macro 'ff'
   66 |     ff(j,1,k){
      |     ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:69:9: note: in expansion of macro 'ff'
   69 |         ff(i,1,n)uzo[i] = 0;
      |         ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:70:9: note: in expansion of macro 'ff'
   70 |         ff(i,1,n){
      |         ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:76:9: note: in expansion of macro 'ff'
   76 |         ff(i,1,n){
      |         ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:84:9: note: in expansion of macro 'ff'
   84 |         ff(i,1,n){
      |         ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:119:5: note: in expansion of macro 'ff'
  119 |     ff(i,1,n){
      |     ^~
tickets.cpp:4:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    4 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
tickets.cpp:121:9: note: in expansion of macro 'ff'
  121 |         ff(j,1,m)row.pb(ans[i][j]);
      |         ^~

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 10 / 10